def mergeSort( A ):
    if len(A)==1: #Base Case
        return
    else:
        middle = len(A)//2  #You could also do int(len(A)/2)

        #Create two temporary lists with COPIES of the two halves
        left = A[:middle]   
        right = A[middle:] 
  
        mergeSort(left) 
        mergeSort(right)

        #Set up indices for where we are in each lists
        frontLeft = 0
        frontRight = 0
        frontMain = 0

        # Copy data from L and R back in to A 
        while frontLeft < len(left) and frontRight < len(right): 
            if left[frontLeft] < right[frontRight]: 
                A[frontMain] = left[frontLeft] 
                frontLeft = frontLeft +1
            else: 
                A[frontMain] = right[frontRight] 
                frontRight = frontRight +1
            frontMain = frontMain + 1
          
        # Checking which pile still has elements left 
        while frontLeft < len(left): 
            A[frontMain] = left[frontLeft] 
            frontLeft += 1
            frontMain += 1
          
        while frontRight < len(right): 
            A[frontMain] = right[frontRight] 
            frontRight += 1
            frontMain += 1

    

import random
from timeit import Timer
original = list(range(3000))
double = list(range(len(original)*2))
random.shuffle(original)
random.shuffle(double)

##Merge Sort
print("Merge Sort")
originalCopy = original[:]
doubleCopy = double[:]

t1 = Timer("mergeSort(originalCopy)", "from __main__ import mergeSort,originalCopy")
res1 = t1.timeit(number=1)
print(f"mergeSort(original) : {res1:15.2f} seconds")

t1 = Timer("mergeSort(doubleCopy)", "from __main__ import mergeSort,doubleCopy")
res2 = t1.timeit(number=1)
print(f"mergeSort(double) : {res2:15.2f} seconds")

print("Doubled the data")
print("Time changed by a factor of "+str(res2/res1))
print()