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)
