count-split-inversions.py

def bruteForce(A):
    counter = 0
    for i in range(len(A)):
        for j in range(i, len(A)):
            if A[i] > A[j]:
                counter += 1
    return counter

def countSplitInversions(B, C):
    i,j,D = 0,0,[]    
    m = len(B)
    n = len(C)
    counter = 0
    while i < m and j < n:
        if B[i] < C[j]:
            D.append(B[i])
            i += 1
        else:
            D.append(C[j])
            j += 1
            counter += len(B[i:])
         
    D = D + B[i:] + C[j:]
    return (D, counter)
        
    



def countInversions(A):
    n = len(A)
    split = n//2
    if n == 1:
        return (A, 0)
    else:
        (B, x) = countInversions(A[:split])
        (C, y) = countInversions(A[split:])
        (D, z) = countSplitInversions(B, C)
        return (D, x + y + z)

G = [0, 2, 4, 1, 3, 5]        
H = [1, 7, 6, 8, 5, 3, 4, 0, 2]


print bruteForce(G)
print countInversions(G)