Counting Inversions in Python

Below is an O(n log(n)) algorithm for counting the number of inversions in an array of distinct positive integers. We call the index pair (i,j) of an array A an inversion provided that i < j and A[i] > A[j]. The idea is to break the array A into a left half L:=A[:n] and a right half R:=A[:n] and then count the number of inversions in L, in R, and the number of split inversions (i,j) where i is less than n and j is greater than or equal to n. If L and R are already sorted then we can easily count the number of split inversions via a slight augmentation to the merge subroutine of merge-sort.

def SortCount(A):
   l = len(A)
   if l > 1:
      n = l//2
      C = A[:n]
      D = A[n:]
      C, c = SortCount(A[:n])
      D, d = SortCount(A[n:])
      B, b = MergeCount(C,D)
      return B, b+c+d
   else:
      return A, 0


def MergeCount(A,B):
   count = 0
   M = []
   while A and B:
      if A[0] <= B[0]: 
         M.append(A.pop(0)) 
      else: 
         count += len(A)
         M.append(B.pop(0)) 
   M  += A + B     
   return M, count