Quick sort and partitioning

Quick sort picks one value, the pivot, and moves every smaller value to its left and every other value to its right. Then the pivot is in its final place, and each side is sorted the same way. It sorts in place and is very fast on average.

Partitioning

Splitting a list around a pivot is called partitioning. The simplest method, Lomuto’s, uses the last value as the pivot and one pass from left to right:

def partition(a, lo, hi):
    p = a[hi]                 # the pivot
    i = lo
    for j in range(lo, hi):
        if a[j] < p:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i] # pivot to its final place
    return i

Each pass looks at a[j]. If it is small, it swaps to position i, the end of the small part, and i moves on. Either way j moves on, so the invariant holds. At the end, swapping the pivot into position i puts it between the two parts.

The whole sort

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    k = partition(a, lo, hi)
    quick_sort(a, lo, k - 1)
    quick_sort(a, k + 1, hi)

Unlike merge sort, all the work happens before the recursive calls, and nothing needs merging afterwards. The pivot is in its final place and never moves again.

Good and bad pivots

If every pivot splits its part roughly in half, the cost is T(n) = 2T(n/2) + n, which is O(n log n). If every pivot is the largest or smallest value, each split leaves n − 1 values on one side: T(n) = T(n − 1) + n, which is O(n²). Step through the second version of the figure: with the last value as pivot, an already sorted list is the worst case.

The fix is to choose the pivot at random (swap a random value into position hi first). Then no input is always bad. The expected number of comparisons is about 1.39 n log₂ n (1.39 times n times the number of times n can be halved), for every input. Even a split as uneven as 10% and 90% at every level still gives O(n log n): the levels go down by a factor of 0.9, so there are only about log n of them.

Many equal values

Lomuto’s partition puts values equal to the pivot all on one side. If every value is the same, every split is as bad as possible, and quick sort becomes O(n²) again, even with random pivots. The fix is a three-way partition: less than, equal to, and greater than the pivot. It is the same three-part split as CORR-P3. The equal part is already in place and is never sorted again.

Lesson 8 uses partitioning to find one value without sorting. Try SORT-P4, The k-th fastest after it.