count_inversions.py

#!/usr/env python


def merge_and_count_split_inversions(A, B, C):
    """ O(n)"""

    i = 0
    j = 0

    inv = 0

    for k in range(len(A) + len(B)):

        # If left node items are done, just fill up remaining right node items
        if i == len(A):
            C[k] = B[j]
            j += 1
            continue

        # If right node items are done, just fill up remaining left node items
        if j == len(B):
            C[k] = A[i]
            i += 1
            continue

        # Compare items in left and right node
        if A[i] < B[j]:
            C[k] = A[i]
            i += 1
        else:
            C[k] = B[j]
            j += 1
            # Number of elements left in first array are split inversions
            inv += len(A[i:])

    return inv


def merge_sort_with_inversions(l):
    """ Uses Divide and Conquer method to sort a list and count inversions"""

    # Base case
    if len(l) == 1:
        return 0

    # split into smaller lists and call recursively - Divide step
    left = l[:len(l)//2]
    right = l[len(l)//2:]
    # note - 'left' and 'right' list variables are *necessary*,
    # they store the updated list (l) when merge is called.
    x = merge_sort_with_inversions(left)
    y = merge_sort_with_inversions(right)

    # merge and update the list with the merge result - Conquer ste
    z = merge_and_count_split_inversions(left, right, l)
    # print "Merge of {} and {} gives {}".format(left, right, l)
    return x + y + z


def main():
    ilist = [4,5,6,2,1,8,9,0]
    #ilist = [1,3,5,2,4,6]

    with open('IntegerArray.txt') as fd:
        inlist = fd.read().split('\r\n')
        dc = inlist.pop()
        ilist = [int(i) for i in inlist]

    print ilist
    inversions = merge_sort_with_inversions(ilist)
    print ilist
    print inversions


if __name__ == "__main__":
    main()