# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, middle, r):
    leftlength = middle - l + 1
    rightlength = r - middle

    # create temporary arrays
    left = []
    right = []

    # Copy data to temp subarrays L[] and R[]
    for i in range(leftlength):
        left.append(arr[l + i])

    for j in range(rightlength):
        right.append(arr[middle + 1 + j])

    i = 0     # Initial index of left subarray
    j = 0     # Initial index of right subarray
    k = l     # Initial index of main array
    # Merge the subarrays into arr[l..r]
    while i < leftlength and j < rightlength :
        if left[i] <= right[j] :
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    # Copy the rest of left array if it remains
    while i < leftlength:
        arr[k] = left[i]
        i += 1
        k += 1

    #Copy the rest of the right array if it remains
    while j < rightlength:
        arr[k] = right[j]
        j += 1
        k += 1

# l is for left index and r is right index of the subject array to be sorted
def mergeSort(arr,l,r):
    if l < r: #need this if statement because it allows to stop when array length is 1
        middle = (l+r)//2

        mergeSort(arr, l, middle)
        mergeSort(arr, middle+1, r)
        merge(arr, l, middle, r)



#TEST
import random
arr = [int(100*random.random()) for i in range(100)]
n = len(arr)
print ("Generated: ", arr)
mergeSort(arr,0,n-1)
print ("\nSorted: ", arr)

#I could not figure out how to keep count of the steps in merge sort; each time a function calls itself,
#it resets the count. But without setting an initial value in the function, it can't add the counts.