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

15 Mar 2005


      On Tue, 15 Mar 2005, Ben Rudiak-Gould wrote:
...
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]
Yes, zipping together one-node lists is a nice idea to prevent dividing as 
in the classic divide&conquere scheme.