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

[Henning Thielemann]

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.