Divide and Conquer: Quicksort

quicksort.py

def partition(A, left, right):
    pivot, j = A[left], left
    for i in range(left + 1, right + 1):
        if A[i] <= pivot:
            j += 1
            A[i], A[j] = A[j], A[i]
    A[left], A[j] = A[j], A[left]
    return j


def quicksort(A, left, right):
    """
    Running time:
    O(nlogn)

    pivot = A[left]
    move i from left + 1 to right maintaining the following invariant:
    A[k] <= x ∀ left + 1 <= k <= j
    A[k] > x ∀ j + 1 <= k <= i
    then move A[left] to its final position
    """
    if left > right:
        return
    k = random.randint(left, right)
    A[k], A[left] = A[left], A[k]
    pivot = partition(A, left, right)
    quicksort(A, left, pivot - 1)
    quicksort(A, pivot + 1, right)