[python] count inversion with mergesort

Coursera Algorithm 강의 첫번째 과제. 단순하게 mergesort를 이용해서 순서를 정할때 거꾸로 정리되는 경우의 수를 체크하는 문제였다.

mergesort를 쓰게 되면 기존에 O(n^2)의 complexity가 O(nlogn)으로 떨어진다. 

def readFile(filename, l):
    with open(filename, "r") as f:
        for line in f:
            l.append(int(line))
    if f.closed == False:
        f.close()

def sortAndCount(A):
    mid = len(A) // 2
    
    if len(A) == 1:
        return A, 0
        
    B, x = sortAndCount(A[:mid])
    C, y = sortAndCount(A[mid:])
    D, z = mergeAndCountSplitInv(B, C, len(A))
    
    return  D, x + y + z

def mergeAndCountSplitInv(B, C, n):
    D = []
    i = 0
    j = 0
    inverse = 0
    
    for k in range(n):
        if i == len(B):
            D.append(C[j])
            j += 1
        elif j == len(C):
            D.append(B[i])
            i += 1
        else:
            if B[i] < C[j]:
                D.append(B[i])
                i += 1
            else:
                D.append(C[j])
                inverse += len(B[i:]) 
                j += 1
    return D, inverse

x = 0
y = 0  
                     
test = []
readFile("IntegerArray.txt", test) 

print sortAndCount(test)[1]