Inversion Count - Merge Sort

Inversion Count - Merge Sort

def inversionCount_2(A):
    def inversionCount_2(A,l,r):
        if l >= r: return 0
        m = (l + r) / 2
        # recurse and store inversion counts for the halfs
        invCount = inversionCount_2(A,l,m) + inversionCount_2(A,m + 1,r)
        merged = []
        i,j = l,m + 1
        while i <= m and j <= r:
            if A[i] < A[j]:
                merged.append(A[i])
                i += 1
            else:
                invCount += m - i + 1 #A[j] < A[i..m]
                merged.append(A[j])
                j += 1
        merged.extend(A[i:m + 1]) # rest of first half
        merged.extend(A[j:r + 1]) # rest of the second half
        for i in xrange(l,r + 1): #copy from aux to Arr
            A[i] = merged[i - l]
        return invCount
    return inversionCount_2(A,0,len(A) - 1)