sorting a list and counting interchanges

[John Machin]

On 6 Apr 2005 15:30:41 -0700, "RickMuller" <rpmuller at gmail.com> wrote:

>I have to sort a list, but in addition to the sorting, I need to
>compute a phase factor that is +1 if there is an even number of
>interchanges in the sort, and -1 if there is an odd number of
>interchanges.
>
>I could write a bubble sort, count the number of interchanges, and
>compute the factor, but I have a feeling that there some
>decorate-sort-undecorate solution buried in this problem somewhere.
>However, I can't see it. Can anyone else help me with this?
>

1. What is an "interchange"?

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.

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