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.
1 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.