# [Haskell-cafe] Parity of the number of inversions of a permutation

Ben Rudiak-Gould Benjamin.Rudiak-Gould at cl.cam.ac.uk
Tue Mar 15 08:54:13 EST 2005

```Henning Thielemann wrote:
> I' searching for a function which sorts the numbers and determines the
> parity of the number of inversions. I assume that there are elegant and
> fast algorithms for this problem (n * log n time steps), e.g. a merge
> sort algorithm.

This is a rather nice little problem. I think this works:

countInversions :: (Ord a) => [a] -> Int

countInversions [] = 0
countInversions xs = snd \$ foldb merge [([x],0) | x <- xs]

merge :: (Ord a) => ([a],Int) -> ([a],Int) -> ([a],Int)

merge (xs,a) (ys,b) =
case merge' (length xs) xs ys of
(zs,c) -> (zs,a+b+c)

merge' 0 [] ys = (ys,0)
merge' n xs [] = (xs,0)
merge' n (x:xs) (y:ys) =
case compare x y of
LT -> case merge' (n-1) xs (y:ys) of (zs,c) -> (x:zs,c)
GT -> case merge' n (x:xs) ys of (zs,c) -> (y:zs,c+n)
EQ -> undefined

foldb :: (a -> a -> a) -> [a] -> a

foldb f [] = undefined
foldb f [x] = x
foldb f xs = foldb f (foldb' f xs)

foldb' f (x1:x2:xs) = f x1 x2 : foldb' f xs
foldb' f xs = xs

-- Ben
```