Simplest Quick Sort Algorithm

A lot of quicksort implementations are hard to follow, because the indexes are shifted around slightly (+1 or -1).  Here's the most intuitive implementation I could write:



# split an array into 3 groups around an arbitrary pivot value (last element):
# [ less than pivot ... equal to pivot ... greater than or equal to pivot ]
def partition(arr, low, high):
    # consolidate any elements smaller than pivot (last element)
    i = low 
    for j in range(low, high):
        if arr[j] < arr[high]:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1 
    # drop pivot into position at middle 
    arr[i], arr[high] = arr[high], arr[i]
    return i

# main function
def quickSort(arr, low, high): 
    if low < high:
        pi = partition(arr, low, high)
        # now, resort new regions around pivot
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)