## 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