sympy/sympy — pull request #1102 by catchmrbharath (2012-03-02 18:33:51+00:00)
Title: Faster algorithm for inversion in Permutation

I have implemented a faster algorithm for inversion if the length of the permutation array is greater than 100. The performance of the new algorithm compared to the old one is as follows :
Code
------
``` python

a = Permutation([i for i in range(100, -1, -1)])
t = time()
r = a.array_form
print _merge_count(r[:], r[:], 0, len(r)-1)
print time()-t
b = Permutation([i for i in range(100, -1, -1)])
t = time()
print b.inversions()
print time()-t
```
Output
---------
```
5050
0.000481843948364
5050
0.000545978546143
```

For 100 numbers, the improvement is not significant. Running the same for 500 numbers, the results are as follows:

Code
-------
``` python

a = Permutation([i for i in range(500, -1, -1)])
t = time()
r = a.array_form
print _merge_count(r[:], r[:], 0, len(r)-1)
print time()-t
b = Permutation([i for i in range(500, -1, -1)])
t = time()
print b.inversions()
print time()-t
```
Output
---------
```
125250
0.00265789031982
125250
0.0123178958893
```
Its 5x faster for input length of 500.

Running it for 1000 length array gives an 10x improvement. As the length of the array increases the performance is better.
The algorithm is based on merge sort.
Ref : http://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm