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

[Ben Rudiak-Gould]

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