inversion_count.py

import time

inv = 0


def mergesort(arr):
    global inv
    if len(arr) <= 1:
        return arr
    else:
        # Use "double divide" to handle odd-length arrays
        m = len(arr) // 2
        # Recursive call FTW!
        left, right = mergesort(arr[:m]), mergesort(arr[m:])
        i, j = 0, 0
        for k in xrange(len(arr)):
            # The core of mergesort
            if i < len(left) and j < len(right):
                if left[i] < right[j]:
                    arr[k] = left[i]
                    i += 1
                else:
                    # Inversion happens, count 'em!
                    inv += len(left) - i
                    arr[k] = right[j]
                    j += 1
            elif i == len(left):
                arr[k:] = right[j:]
                break
            elif j == len(right):
                arr[k:] = left[i:]
                break
        return arr


# j4f
def runtime(func, args):
    now = time.time()
    func(args)
    return time.time() - now


if __name__ == '__main__':
    # Load file into readable integer array
    with open('array.txt') as f:
        data = f.readlines()
    data = [int(num.rstrip()) for num in data]
    # Start countint inversions
    mergesort(data)
    print inv