inversions.py

def read_file(fileName):
    nums= []
    with open(fileName, "r") as fp:
        for num in fp:
            nums.append(int(num))
    return nums


def inv_count_brute_force(arr, n):
    inv_count = 0
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] > arr[j]:
                inv_count += 1
    return inv_count

def merge_sort(arr, n):
    tmp = []
    return _merge_sort(arr, tmp, 0, len(arr) - 1)

def _merge_sort(arr, tmp, left, right):
    # mid, inv_count = 0
    mid = 0
    inv_count = 0
    if (right > left):
        mid = (right + left) / 2
        inv_count = _merge_sort(arr, tmp, left, mid)
        inv_count += _merge_sort(arr, tmp, mid + 1, right)
        inv_count += merge(arr, tmp, left, mid + 1, right)
    return inv_count

def merge(arr, tmp, left, mid, right):
    i = left
    j = mid
    k = right
    inv_count = 0

    while (i <= mid - 1) and (j <= right):
        if arr[i] <= arr[j]:
            k += 1
            i += 1
            tmp[k] = arr[i]
        else:
            k += 1
            j += 1
            tmp[k] = arr[j]
            inv_count = inv_count + (mid - i)
    
    while i <= (mid - 1):
        k += 1
        i += 1
        tmp[k] = arr[i]

    while j <= right:
        k += 1
        j += 1
        tmp[k] = arr[j]

    i = left
    while i <= right:
        arr[i] = tmp[i]
        i += 1
    return inv_count
        
arr = read_file("./nums.txt")
inversions = inv_count_brute_force(arr, 100000)
print("Number of inversions:", inversions)