## Translation of CLRS pseudocode into Python.
def quicksort(a, p, r):
"""sorts elements a[p] through a[r] into nondecreasing order"""
if r > p:
q = partition(a, p, r)
quicksort(a, p, q-1)
quicksort(a, q+1, r)
def partition(a, p, r):
"""partitions the range a[p] through a[r] and returns pivot position"""
x = a[r]
i = p-1 # everything to the right of i, up to j, is >x
# everything starting with p, up through i, is <= x
for j in range(p, r):
if a[j] <= x:
i = i + 1
a[i], a[j] = a[j], a[i]
q = i+1
a[q], a[r] = a[r], a[q]
return q