import random
#function to merge two sorted arrays and count reverse in a pair
def merge(arr, temp, left, mid, right):
    i = left #index for left subarray
    j = mid #index for right subarray
    k = right #index for resultant merged subarray
    reverse_count = 0

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

    #copy the remaining elements of left subarray
    while(i <= mid - 1):
        temp[k] = arr[i]
        k = k + 1
        i = i + 1
    
    #copy the remaining elements of right subarray
    while(j <= right):
        temp[k] = arr[j]
        k = k + 1
        j = j + 1
    #copy back the merged elements to the original array
    for i in range(left, right):
        arr[i] = temp[i]
    
    return reverse_count

def merge_sort_helper(arr, temp, left, right):
    mid = 0
    reverse_count = 0

    if(right > left):
        mid = (right + left) / 2

        #inversion count is the sum of reverse in a pair in left part , right part, and number of reverse in a pair in merging
        reverse_count = reverse_count + merge_sort_helper(arr, temp, left, mid)
        reverse_count = reverse_count + merge_sort_helper(arr, temp, mid + 1, right)

        #merge two parts and adding to reverse_count
        reverse_count = reverse_count + merge(arr, temp, left, mid + 1, right)

    return reverse_count

def merge_sort(arr, array_size):
    temp = ["NULL"] * array_size
    return merge_sort_helper(arr, temp, 0, array_size - 1)

def main():
    n = 100
    arr = ["NULL"] * n
    for i in range(len(arr)):
        arr[i] = random.randint(0, 500)
    
    print("Our inital array is: ")
    for i in range(len(arr)):
        print(arr[i])
    
    print("Our number of reverses in a pair is :" + str(merge_sort(arr, n)))
    return 0

main()