Quicksort & PARTITION

◈ 5 cards

In-place divide-and-conquer with a trivial combine; the four-region PARTITION invariant; best/avg Θ(n lg n) but worst Θ(n²) on sorted input.

All the work is in the divide

Quicksort is divide-and-conquer where partitioning is everything and the combine step does nothing. To sort $A [p .. r]$ : PARTITION picks a pivot, rearranges so everything $\leq$ pivot is on its left and everything $>$ pivot is on its right, and returns the pivot's final index $q$ . Then recurse on $A [p .. q - 1]$ and $A [q + 1.. r]$ . Because the pivot is already in its final sorted slot and each side is sorted in place, no merge is needed — that is why quicksort sorts in place.

PARTITION and its four-region invariant

Lomuto's PARTITION takes $x = A [r]$ as the pivot and scans $j$ from $p$ to $r - 1$ , maintaining four regions:

$A [p .. i]$ — known $\leq x$ (the low side),
$A [i + 1.. j - 1]$ — known $> x$ (the high side),
$A [j .. r - 1]$ — not yet examined,
$A [r] = x$ — the pivot, parked at the end.

When $A [j] \leq x$ , increment $i$ and swap $A [i] \leftrightarrow A [j]$ (grow the low side); otherwise just advance $j$ (grow the high side). After the loop, swap $A [i + 1] \leftrightarrow A [r]$ to drop the pivot between the two sides and return $i + 1$ . The loop does $O (1)$ work per element, so PARTITION is $Θ (n)$ .

When it wins and when it loses

Best case: every split is balanced (size $\leq n /2$ each). $T (n) = 2 T (n /2) + Θ (n) = Θ (n l g n)$ .
Worst case: every split is $0$ vs $n - 1$ . $T (n) = T (n - 1) + Θ (n) = Θ (n^{2})$ .
Average case: $Θ (n l g n)$ — and remarkably, any constant-ratio split (even 9-to-1) still gives $Θ (n l g n)$ , because the recursion tree stays $Θ (l g n)$ deep with $Θ (n)$ work per level.

The worst case is triggered by already-sorted (or reverse-sorted) input when the pivot is always $A [r]$ : the pivot is always the max (or min), so one side is always empty. Sorted input — the easy case for insertion sort — is the worst case for fixed-pivot quicksort. The next lesson fixes this with randomization.

Worked example

PARTITION on $⟨ 2, 8, 7, 1, 3, 5, 6, 4 ⟩$ with pivot $4$ returns index $3$ and leaves $⟨ 2, 1, 3, 4, 7, 5, 6, 8 ⟩$ — everything left of index 3 is $\leq 4$ , everything right is $> 4$ , and $4$ sits in its final place. Running full quicksort then yields the sorted list. Both runnable exercises reproduce this.

The four-region invariant, mid-scan. Everything left of i is ≤ x, everything between i and j is > x, everything from j on is unexamined, and x waits at the end.

Sorted input, pivot = last element. Each level removes exactly one element, so there are n levels of Θ(n) work — Θ(n²), the same cost as insertion sort.