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

[Henning Thielemann]

I think it is a quite popular problem. I have a permutation and I want to 
count how often a big number is left from a smaller one. More precisely 
I'm interested in whether this number is even or odd. That's for instance 
the criterion to decide whether Lloyd's shuffle puzzle is solvable or not.

Example:
   1 4 3 2

I can choose six pairs (respecting the order) of numbers out of it, namely 
(1,4) (1,3) (1,2) (4,3) (4,2) (3,2), where in the last three pairs the 
first member is greater than the second one. Thus I have 3 inversions and 
an odd parity.

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. A brute force solution with quadratic time consumption is

countInversions :: (Ord a) => [a] -> Int
countInversions = sum . map (\(x:xs) -> length (filter (x>) xs)) . init . tails