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.