Os dois códigos abaixo fazem isso. O primeiro baseado em força bruta comparando todos os termos. O segundo usando explicitamente o merge_sort que é usado para ordenar sequências.
import numpy as np
# Algoritmo forca bruta
def counting_inversions(sequence):
n=sequence.size
numberInversions=0
for i in range(0,n):
for j in range(i+1,n):
if(sequence[i]>sequence[j]):
numberInversions=numberInversions+1
return numberInversions
# Algoritmo usando o paradigma de divisao e conquista (de fato, usando merge_sort)
def merge(a,b):
na=a.size
nb=b.size
c=np.empty([na+nb],int)
i=0
j=0
z=0
count=-1;
while((i<=na-1)and(j<=nb-1)):
count=count+1
if(a[i]<b[j]):
c[count]=a[i]
i=i+1
else:
c[count]=b[j]
z=z+(na-i)
j=j+1
if(count<na+nb-1):
if(i<=na-1):
for k in range(count+1,na+nb):
c[k]=a[i]
i=i+1
else:
for k in range(count+1,na+nb):
c[k]=b[j]
j=j+1
return (c,z)
def merge_sort(a):
n=a.size
x=0
y=0
z=0
if(n>1):
b=a[0:n//2]
c=a[n//2:n]
[b,x]=merge_sort(b)
[c,y]=merge_sort(c)
[a,z]=merge(b,c)
return (a,x+y+z)
a=np.array([5,6,4,3,1,2])
print "numberInversions="
print counting_inversions(a)
print "numberInversionsRecursive="
print merge_sort(a)