sorting a list and counting interchanges

[Raymond Hettinger]

[RickMuller]
> 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.

It occurs to me that the previously posted comparison count won't do it.

The only idea that comes to mind is to do a selection sort and count the number
of swaps.

a = [1,10,2,7]
parity = 1
for i in xrange(len(a)-1):
    x = a[i]
    lowest = i
    for j in xrange(i, len(a)):
        if a[j] < a[lowest]:
            lowest = j
    if i != lowest:
        a[i], a[lowest] = a[lowest], a[i]
        parity = -parity
        print 'swapping %d with %d.  parity is %d' % (i, lowest, parity)
print parity, a


Raymond