sorting a list and counting interchanges

[Raymond Hettinger]

[John Machin]
> 2. Without a definition that refers only to to the input and output,
> one would have to say that "interchange" implies "event" and so the
> number of interchanges would depend on the sorting method.

As the dataset contains no duplicates, the parity will be the same irrespective
of sorting method.

> 3. Of what practical use (or even esoteric academic interest) is the
> parity of the number of interchanges?

I presume the goal is academic, determining whether a permutation is a member of
the alternating group of even permutations (A4, A5, ...).  For some problems,
that is a useful invariant.  For instance, iirc, the parity determines whether a
given 15 puzzle arrangement is solvable.


Raymond