sorting a list and counting interchanges

[Paul Rubin]

John Machin <sjmachin at lexicon.net> writes:
> 1. What is an "interchange"?

Swapping two elements during the sort.

> 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.

The number of interchanges depends on the sorting method, but whether
the number is odd or even is invariant.  Every permutation of elements
is either an odd permutation or an even permutation.

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

It is of considerable interest in combinatorics.  The group of even
permutations on N elements is called the alternating group A(N).
It's an order-2 subgroup of the symmetric group S(N) which is the
group of all the permutations on N elements.  The odd permutations
are of course a coset of A(N).