sorting a list and counting interchanges

[Paul Rubin]

"Jordan Rastrick" <jrastrick at student.usyd.edu.au> writes:
> def mycmp(x,y):
>    global phase
>    c = cmp(x,y)
>    if c > 0: # i.e. a swap will be performed in the sort
>        phase = -phase
>    return c

That doesn't necessarily work.  You don't know that c>0 will always
result in a swap.  You don't know that the sorting algorithm necessarily
never swaps an element with itself.  You have to find all the cycles in
the permutation and count the length of each one.  Is this a homework
problem?  If yes, the above should be enough of a hint.