import random, sys

def bubblesort(a):
    swaps = 0
    for x in range(1, len(a)):
        for i in range(0, len(a) - x):
            if(a[i] > a[i + 1]):
                swaps += 1
                buf = a[i]
                a[i] = a[i + 1]
                a[i + 1] = buf
    return swaps


def merge(arr, left, right):
    i = 0
    j = 0
    ret = 0
    while( i < len(left) or j < len(right)):
        if(i == len(left)):
            arr[i + j] = right[j]
            j += 1
        elif j == len(right):
            arr[i + j] = left[i]
            i += 1
        elif left[i] <= right[j]:
            arr[i + j] = left[i]
            i += 1
        else:
            arr[i + j] = right[j]
            ret += len(left) - i
            j += 1
    return ret


def invcount(arr):
    if(len(arr) < 2): return 0
    m = (len(arr) + 1) // 2
    left = list(arr[:m])
    right = list(arr[m:])
    return invcount(left) + invcount(right) + merge(arr, left, right)


arr = list(range(1, 8))
random.shuffle(arr)
arr2 = list(arr)
print(arr)
print(invcount(arr))
print("Done", arr)

print(arr2)
print(bubblesort(arr2))
print("Done", arr2)