sorting a list and counting interchanges

[Paul Rubin]

Peter Nuttall <p.s.nuttall at durham.ac.uk> writes:
> I would just write a quicksort and have a counter in the swap function.
> A cunning way to do it would be to multiply the counter by -1 for each
> swap. if you want I can write what I had in mind. Wikipedia has a good
> article of quicksort.

Writing a sorting function from scratch for this purpose seems like
reinventing the wheel.  Tim's answer of simply counting the cycles
(without having to pay attention to their length) is really clever.  I
didn't realize you could do that.  Proving it is a cute exercise.
Hint: any cycle of odd length has an even number of swaps, and any
cycle of even length has an odd number of swaps (another exercise).

http://en.wikipedia.org/wiki/Even_and_odd_permutations
http://en.wikipedia.org/wiki/Permutation