in reply to Re: sort function and parity of the permutation.
in thread sort function and parity of the permutation.

I think it's about the sign function sgn(σ) of permutations, which tells the parity of necessary transpositions (swapping just two elements)

IMHO it should be simple to reproduce and count these transpositions by comparing input and output of the sorting so it's O(n).

Faint memories tell me that counting the numbers of elements which need to be "pushed forward" is already enough.¹

Cheers Rolf

¹) Never mind, this was wrong! For {4,3,2,1} it's even and for {4,3,1,2} it's odd.

  • Comment on Re^2: sort function and parity of the permutation.

In Section Seekers of Perl Wisdom