Pivot Strategies and Randomized Quicksort

Quicksort's efficiency hinges entirely on how well the pivot splits the array. If every partition splits an array of size $n$ into two halves of roughly $n/2$, the recursion tree has depth $O(\log n)$ and the total work is $O(n \log n)$. If instead every partition peels off just one element (the worst possible split), the recursion has depth $\Theta(n)$ and the total work is $\Theta(n^2)$. The pivot strategy is precisely the mechanism that determines which of these regimes we land in. The naive strategy — always use `A[lo]` or `A[hi]` as the pivot — is dangerous because it is input-dependent in a predictable way: on already-sorted or reverse-sorted arrays (extremely common in practice), it produces the worst possible split at every level of recursion, giving $\Theta(n^2)$ time. Median-of-three improves this by examining three elements — typically `A[lo]`, `A[mid]`, `A[hi]` — and using their median as the pivot. This is a deterministic heuristic: it defeats sorted and reverse-sorted inputs cheaply (three comparisons per call), but a sufficiently informed adversary who knows the exact rule can still construct an input that forces $\Theta(n^2)$ behavior, because the rule is still a fixed function of array positions.

Randomized quicksort severs the link between input and pivot choice entirely. At each recursive call, the pivot is chosen uniformly at random from the current subarray (equivalently, the subarray is randomly shuffled once up front, or a random index is swapped into the pivot position before every partition). Because the algorithm's randomness — not the input's structure — determines the split, no fixed input can force bad behavior with high probability, and the expected running time is $O(n \log n)$ for every input, including ones an adversary designs after seeing the source code (though not after seeing the random seed). This distinction — deterministic worst-case-per-input vs. randomized worst-case-over-all-runs — is the conceptual heart of the article, and it is proved rigorously using indicator random variables, a technique that decomposes a complicated random quantity (total comparisons) into a sum of simple 0/1 random variables whose expectations are easy to compute individually.

Partitioning (assumed from Quicksort and Partitioning) rearranges a subarray around a pivot value so that everything less than the pivot comes before it and everything greater comes after; the pivot lands at its final sorted position. The pivot strategies below differ only in which element is chosen as the pivot before partitioning runs.

Median-of-three. Look at `A[lo]`, `A[mid]`, `A[hi]` where `mid = lo + (hi - lo) / 2`. Find their median by a constant number of comparisons, swap it into a fixed position (commonly `A[lo]` or `A[hi]`, whichever the partition routine expects), then partition as usual. This costs O(1) extra work per call and reliably avoids the worst case on already-sorted, reverse-sorted, and "organ-pipe" inputs, which are the most common accidentally-adversarial inputs in practice.

Randomized pivot selection. Before partitioning a subarray `A[lo..hi]`, draw a uniformly random index `r` in `[lo, hi]`, swap `A[r]` with `A[hi]` (or wherever the partition scheme expects its pivot), and then run the ordinary deterministic partition procedure. Every recursive call makes an independent random choice. ``` // Lomuto-style partition, pivot assumed to be at A[hi] PARTITION(A, lo, hi): pivot = A[hi] i = lo - 1 // boundary of "less than pivot" region for j = lo to hi - 1: if A[j] <= pivot: i = i + 1 swap(A[i], A[j]) swap(A[i + 1], A[hi]) return i + 1 // final index of the pivot RANDOMIZED-PARTITION(A, lo, hi): r = RANDOM-INTEGER(lo, hi) // uniform over {lo, ..., hi} swap(A[r], A[hi]) return PARTITION(A, lo, hi) RANDOMIZED-QUICKSORT(A, lo, hi): if lo < hi: p = RANDOMIZED-PARTITION(A, lo, hi) RANDOMIZED-QUICKSORT(A, lo, p - 1) RANDOMIZED-QUICKSORT(A, p + 1, hi) // Median-of-three variant: choose pivot deterministically, then partition MEDIAN-OF-THREE-QUICKSORT(A, lo, hi): if lo < hi: mid = lo + (hi - lo) / 2 m = MEDIAN-INDEX(A, lo, mid, hi) // index of median of the 3 values swap(A[m], A[hi]) // move median into pivot slot p = PARTITION(A, lo, hi) MEDIAN-OF-THREE-QUICKSORT(A, lo, p - 1) MEDIAN-OF-THREE-QUICKSORT(A, p + 1, hi) ``` Two important edge cases: the base case `lo >= hi` correctly handles empty (`lo > hi`) and single-element (`lo == hi`) subarrays by doing nothing, and `PARTITION` correctly handles all-equal elements because the condition `A[j] <= pivot` (rather than strict `<`) keeps the partition balanced instead of degenerating to a one-sided split on arrays of duplicates.

Correctness. Both variants are correct sorting algorithms because pivot choice never affects the correctness of partitioning or recursion — only its balance. `PARTITION` is correct by the loop invariant: at the top of each iteration of the `for` loop, `A[lo..i]` contains only elements `<= pivot` and `A[i+1..j-1]` contains only elements `> pivot`; this invariant holds initially (both regions empty), is maintained by each swap, and at termination (`j = hi`) implies the final swap places the pivot correctly between the two regions. `RANDOMIZED-PARTITION` only relabels which element occupies the pivot slot before calling this unchanged, already-correct routine, so randomization cannot break correctness — it can only change which split is produced, hence only running time. The recursion terminates because each call strictly shrinks `hi - lo`, and the base case `lo >= hi` covers 0- and 1-element subarrays exactly.

Worst case. Both median-of-three and randomized quicksort still have $\Theta(n^2)$ worst-case time. Median-of-three fails on adversarially constructed "median-of-three killer" sequences; randomized quicksort fails only on the astronomically unlikely event that the random pivots happen to always be extreme. What changes is not the worst case itself but its probability.

Expected-time analysis of randomized quicksort — the indicator variable argument. Let $A$ contain $n$ distinct elements, and let $z_1 < z_2 < \cdots < z_n$ denote them in sorted order (we only use this labeling for analysis; the algorithm sees no such order). Quicksort's total work is dominated, up to constant factors, by the number of comparisons performed during all partition calls. A key structural fact: each pair $(z_i, z_j)$, $i < j$, is compared at most once, and it is compared exactly when either $z_i$ or $z_j$ is chosen as a pivot while the other is still in the same subarray as it — equivalently, when $z_i$ or $z_j$ is the first element of $\{z_i, z_i+1, \dots, z_j\}$ chosen as a pivot (elements strictly between them, if any is picked first, separates $z_i$ and $z_j$ into different subarrays forever, and they are never compared). Define the indicator random variable

The total number of comparisons is

By linearity of expectation,

Consider the set $Z_{ij} = \{z_i, z_{i+1}, \dots, z_j\}$, of size $j - i + 1$. Because pivots are chosen uniformly at random and independently of value, at the moment the first pivot from $Z_{ij}$ is chosen, that choice is uniform over $Z_{ij}$ (every element of $Z_{ij}$ is equally likely to be the one selected first, since randomness is symmetric across all elements still in the same subarray). $z_i$ and $z_j$ are compared exactly when this first-chosen pivot is $z_i$ or $z_j$ themselves, which happens with probability

Substituting and letting $k = j - i + 1$ range over subarray sizes:

using the standard bound $\sum_{k=2}^n 1/k = O(\log n)$ (the harmonic series). Hence:

and since each comparison does $O(1)$ additional work, the expected running time of randomized quicksort is $O(n \log n)$ on every input — no assumption of random input data is needed, because the randomness lives entirely inside the algorithm.

Why this beats a naive "average-case" argument. A common but weaker claim is "quicksort is $O(n \log n)$ on average, assuming random input." That statement says nothing about a specific fixed input handed to you by a user, a file, or an adversary. Randomized quicksort's guarantee is stronger: for a fixed, arbitrary input, if you re-run the algorithm many times (with fresh randomness each time), the expected time over those runs is $O(n \log n)$, and — via concentration arguments beyond this derivation — the running time is $O(n \log n)$ with high probability, not merely in expectation. This is what makes randomization a genuine defense against adversarial or accidentally-structured input, which median-of-three cannot fully provide.

Space. In-place partitioning uses $O(1)$ extra space per call, but recursion itself costs stack space equal to recursion depth. Naive recursion on both children can require $\Theta(n)$ stack depth in the worst case; the standard fix — recurse on the smaller partition and loop (tail-call) on the larger — guarantees $O(\log n)$ stack depth even in the worst case, which is why production implementations always include this refinement alongside pivot randomization.

Consider the array `A = [1, 2, 3, 4, 5, 6, 7, 8]` — already sorted, the classic killer input for a "pivot = last element" strategy.

Naive pivot (always `A[hi]`). Partitioning `[1..8]` around pivot `8` yields split sizes $7$ and $0$; recursing on the $7$-element sorted subarray again splits $6$ and $0$; and so on. Total comparisons: $7 + 6 + 5 + \cdots + 1 = 28 = \Theta(n^2)$ work for $n = 8$ — the degenerate chain shown in the figure above.

Median-of-three. `lo=0, mid=3, hi=7` gives values `A[0]=1, A[3]=4, A[7]=8`; the median is `4`, swapped into the pivot slot. Partitioning around `4` splits `[1,2,3]` (size 3) from `[5,6,7,8]` (size 4) — a near-perfect split on this input, recovering $O(n \log n)$ behavior. (A dedicated median-of-three-killer sequence can still defeat this rule, but plain sorted/reverse-sorted input cannot.)

Randomized pivot — one concrete run. Suppose the random draws (indices into the current subarray, 0-indexed) are: first call picks index `2` (value `3`), and so on. Trace:

Total comparisons across all partition calls: $7$ (step 1) $+ 1$ (step 2) $+ 3$ (step 3) $+ 1$ (step 4) $+ 1$ (step 5) $= 13$, versus $28$ for the naive fixed-pivot run on the same sorted array — despite this being only one random trial, not even a particularly lucky one. Different random seeds give different comparison counts, but the expected count over all seeds, by the derivation above, is $O(n \log n)$; no seed can be forced by the input alone, which is exactly the property the naive strategy lacks.

Quicksort itself was invented by Tony Hoare in 1959–1960 while he was a visiting student in Moscow, originally designed to sort words for a machine translation project; the recursive partitioning idea and its in-place efficiency made it, decades later, still one of the most widely used sorting algorithms in practice. The randomization refinement and its rigorous expected-time analysis via indicator random variables were developed and popularized through the work of Robert Sedgewick and later crystallized in the algorithms-textbook tradition associated with Cormen, Leiserson, Rivest, and Stein, whose treatment of randomized quicksort became the canonical teaching proof of the $O(n\log n)$ expected bound.

Randomized and median-of-three pivoting are not academic footnotes — they are load-bearing components of real infrastructure. The C++ Standard Library's `std::sort` is typically implemented as introsort, a hybrid that runs quicksort-style partitioning (often with median-of-three or similar pivot selection) but falls back to heapsort if recursion depth exceeds a logarithmic bound, guaranteeing worst-case $O(n \log n)$ while keeping quicksort's excellent constant factors in the common case. Many language runtimes' general-purpose sort routines historically used variants of these ideas until largely shifting to hybrid merge/insertion sort schemes (e.g., Timsort) for stability and adaptive performance on partially-sorted data — a design choice motivated by exactly the kind of worst-case analysis this article develops. Database engines that implement in-memory sort operators for `ORDER BY` clauses, and language-level `sort()` implementations across ecosystems, use randomized or hybrid pivot selection specifically to prevent denial-of-service attacks in which an adversary submits crafted input designed to trigger quadratic behavior. The indicator-random-variable proof technique itself recurs throughout randomized algorithm design — it is the same tool used to analyze randomized Linear-Time Selection (finding the median or $k$-th order statistic in expected linear time), skip lists, and hashing with random pivots or random tables, making this article's central proof idea a template for an entire family of randomized algorithms.

:::quiz[In the harmonic-sum derivation of E[comparisons], what does the term 2/(j-i+1) represent?]

• The probability that z_i and z_j end up in the same final sorted position
• The probability that z_i or z_j is the first pivot chosen from the set of elements between them, inclusive ✓
• The expected number of recursive calls involving both z_i and z_j
• The fraction of the array that lies between z_i and z_j

Ask the tutor: How does the indicator-variable proof change if we analyze randomized quickselect instead of full quicksort?