inversions.py

#!/usr/bin/env python

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

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

#test cases
A = [1, 3, 2, 4]
print sort_and_count(A, len(A))
A = [1, 3, 2]
print sort_and_count(A, len(A))
A = [1, 3, 5, 2, 4, 6]    
print sort_and_count(A, len(A))
data = [int(line.strip()) for line in open("IntegerArray.txt", 'r')]
t = sort_and_count(data, len(data))
print t[1]