def quickSort( A , low, high ):
    if low < high:
        pp = partition(A,low,high)
        quickSort(A,low,pp-1)
        quickSort(A,pp+1,high)
        
        
def partition( A , low, high ):
    pivot = A[high]
    splitIndex = low-1
    
    for j in range(low,high+1):
        if A[j] < pivot:
            splitIndex = splitIndex+1
            A[splitIndex] , A[j] = A[j],A[splitIndex]
    A[splitIndex+1] , A[high] = A[high],A[splitIndex+1]
    return splitIndex +1

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

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

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

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

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