Partitioning around a pivot

After this page, you should be able to:

• Trace the four regions in the inclusive-range partition contract.

• Explain why a correct partition need not be stable or fully sorted.

Builds on: Sorting contracts and list indexing from Topic 1.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

Teaching sorts retain their mutation/return policy: JavaScript mutators return undefined and Julia teaching mutators return nothing. Built-in sort APIs are shown separately: JavaScript sort and Julia sort! return their mutated arrays. The Timsort/Powersort discussion describes Python’s implementation, not the algorithms used by the other runtimes.

Classification before sorting¶

Choose a value called a pivot. A partition operation reorganises a range so values on one side satisfy one comparison with the pivot and values on the other side satisfy the opposite comparison. Neither side must be internally sorted.

Here we follow the lecture’s rule: keys less than or equal to the pivot go left; larger keys go right. Other partition schemes use different tie rules and return different boundaries. Their recursion contracts must be read separately.

A precise contract¶

The code uses an inclusive range lo..hi. It selects a[hi] as pivot and returns its final index p. Afterwards:

• a[lo:p] contains keys at most the pivot;

• a[p] is the selected pivot;

• a[p+1:hi+1] contains keys greater than the pivot;

• the range contains the same records, and positions outside it are unchanged.

Python implementation¶

def partition(a, lo, hi):
    pivot = a[hi]
    boundary = lo
    for scan in range(lo, hi):
        if a[scan] <= pivot:
            a[boundary], a[scan] = a[scan], a[boundary]
            boundary += 1
    a[boundary], a[hi] = a[hi], a[boundary]
    return boundary

function partition(a, lo, hi) {
    const pivot = a[hi];
    let boundary = lo;
    for (let scan = lo; scan < hi; scan++) {
        if (a[scan] <= pivot) {
            [a[boundary], a[scan]] = [a[scan], a[boundary]];
            boundary++;
        }
    }
    [a[boundary], a[hi]] = [a[hi], a[boundary]];
    return boundary;
}

function partition!(a, lo, hi)
    pivot = a[hi]
    boundary = lo
    for scan in lo:hi-1
        if a[scan] <= pivot
            a[boundary], a[scan] = a[scan], a[boundary]
            boundary += 1
        end
    end
    a[boundary], a[hi] = a[hi], a[boundary]
    return boundary
end

Call this only with 0 <= lo <= hi < len(a). hi is inclusive here, although Python slices and range exclude their stop index. The scan excludes hi so the pivot stays in place until the final swap.

Four regions explain the scan¶

Before each comparison, a[lo:boundary] contains keys at most the pivot; a[boundary:scan] contains larger keys; a[scan:hi] is unknown; and a[hi] holds the pivot.

If the scanned key is larger, extend the larger-key region by advancing the scan. Otherwise, swap it with the first larger-key position and advance boundary as well. If that region is empty, the swap is with the same position and is harmless.

Once no unknown values remain, swap the pivot with the first larger key. For [7, 2, 6, 3, 5], the result is [2, 3, 5, 7, 6] with p = 2. The right side remains unsorted, yet partitioning is correct.

Cost and ties¶

On a range of $m$ items, the scan makes exactly $m-1$ pivot comparisons and uses constant additional space. Its time is $\Theta(m)$. This is a Lomuto-style partition.

Equal keys go left in this version. If all keys equal the pivot, boundary reaches hi and the pivot stays at the right end. That is a valid partition but creates a very uneven recursive split. The swaps can also reorder equal-key records: partitioning [2_A, 2_B, 1] produces [1, 2_B, 2_A] when comparisons use the numeric key.

Implementation choices and use¶

The last-element pivot makes traces deterministic. Inclusive bounds must match the recursive caller; substituting a Hoare-style boundary without changing that caller is unsafe. This helper returns an index and mutates only its selected range; it is not a complete sorting function. Its O(1) workspace and lack of stability are properties of this scheme.

Check your understanding¶

Predict the answer before opening the explanation.

1. Why is [2,3,5,7,6] a valid result around pivot 5?

2. How many pivot comparisons does partition make for m items?

Next: Quicksort, which recursively sorts the two sides.