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

[Henning Thielemann]

On Fri, 11 Mar 2005, William Lee Irwin III wrote:

> On Wed, Mar 09, 2005 at 12:42:09PM +0100, Henning Thielemann wrote:

>> I'm 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
>
> That's not a permutation, that's a cycle. Permutations are sets of
> disjoint cycles (which commute).

???

A permutation is a bijective function (here on a finite set), isn't it? 
Ok, the list representation is not immediately a permutation. But why a 
cycle?