Quicksort in Python

Quicksort is divide and conquer sorting algorithm.

Working:
A quick sort first selects a value, which is called the pivot value.
The role of the pivot value is to assist with splitting the list.
The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.
Expected Running time:O(nlogn)
Worstcase :O(n^2)

Advantages:
1.Good Cache Performance
2.Good Parallel Performance


Quick sort has two phase:
1.Partition Phase
def partition(myList, start, end):
    pivot = myList[start]
    left = start+1
    right = end
    done = False
    while not done:
        while left <= right and myList[left] <= pivot:
            left = left + 1
        while myList[right] >= pivot and right >=left:
            right = right -1
        if right < left:
            done= True
        else:
            # swap places
            temp=myList[left]
            myList[left]=myList[right]
            myList[right]=temp
    # swap start with myList[right]
    temp=myList[start]
    myList[start]=myList[right]
    myList[right]=temp
    return right

2.Sort Phase
def quicksort(myList, start, end):
    if start < end:
        # partition the list
        pivot = partition(myList, start, end)
        # sort both halves
        quicksort(myList, start, pivot-1)
        quicksort(myList, pivot+1, end)
    return myList