Although Recipe 578227 was straight-forward to derive, I came across this Stack Overflow answer that gives another method for generating the sign based on comparing the perm and the sorted perm.
Python, 13 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 | def perm_parity2(a):
'''\
Using algorithm from http://stackoverflow.com/questions/337664/counting-inversions-in-an-array/6424847#6424847
But substituting Pythons in-built TimSort'''
a = list(a)
b = sorted(a)
inversions = 0
while a:
first = a.pop(0)
inversions += b.index(first)
b.remove(first)
return -1 if inversions % 2 else 1
|
I have implemented the method in the code, but I use Pythons in-built sort implementation instead of their mergesort.
I timed this and the previous function on finding the sign of the same random shuffle of 10, 20, 30,..110 numbers. The old algorithm is of worse time complexity (in blue).
.
The image did not come through above. Try this instead.