quicksort.py

# http://en.wikipedia.org/wiki/Quicksort

def quicksort(data):
    def partition(array, left, right, pivotIndex):
        pivotValue = array[pivotIndex]
        array[pivotIndex], array[right] = array[right], array[pivotIndex]
        storeIndex = left
        for i in range(left, right):
            if array[i] < pivotValue:
                array[i], array[storeIndex] = array[storeIndex], array[i]
                storeIndex += 1
        array[storeIndex], array[right] = array[right], array[storeIndex]
        return storeIndex

    def sort(array, left, right):
        if left < right:
            pivotNewIndex = partition(array, left, right, left + (right - left) / 2)
            sort(array, left, pivotNewIndex -1)
            sort(array, pivotNewIndex + 1, right)

    sort(data, 0, len(data)-1)