linear time partition

gistfile1.py

def exchange(a, i, j):
    a[i], a[j] = a[j], a[i]

def partition(a, x):
    n = len(a)
    i = 0
    j = 0
    k = n
    while j < k:
        if a[j] < x:
            exchange(a, i, j)
            i += 1
            j += 1
        elif a[j] == x:
            j += 1
        else:
            k -= 1
            exchange(a, j, k)
    return slice(0, i), slice(i, k), slice(k, n)