Quick Sort

• ave time complexity O(nlogn)
• worst case O(n^2)
• in-place
• better choice!

def quickSort(A, start, end):
    if start >= end:
        return
    pIndex = partition(A, start, end)
    quickSort(A, start, pIndex-1)
    quickSort(A, pIndex+1, end)

def partition(A, start, end):
    pivot = A[end] # pick last one as pivot
    pIndex = start
    for i in range(start, end): # till end - 1
        if A[i] < pivot:
            A[i], A[pIndex] = A[pIndex], A[i]
            pIndex += 1
    A[pIndex], A[end] = A[end], A[pIndex] # get pivot here
    return pIndex