Analysing Quicksort

Quicksort is the algorithm that shouldn't work. Its worst case is a quadratic catastrophe, it can be toppled by an already-sorted array, and yet it is, in practice, the fastest general comparison sort we have — the one hiding inside your language's standard library. Understanding why is a masterclass in the whole toolkit of this course: recurrences, the difference between worst and average case, indicator random variables, and the almost magical effect of a single random choice.

We will pin down three numbers: the worst case (\Theta(n^2)), the best case (\Theta(n\log n)), and — the crown jewel — the expected case (\Theta(n\log n)), proved with an argument so clean it fits on a postcard. Then we see how a random pivot makes that expected bound hold on every input, promoting quicksort from a gamble on nice data to a robust randomised algorithm.

Recap: partition, then conquer

Quicksort is divide-and-conquer with all the work in the divide step. Pick a pivot, partition the array so everything smaller sits left of it and everything larger sits right, then recurse on the two sides. The pivot lands in its final sorted position, and — unlike merge sort — there is no combine step at all.

function quicksort(a: number[], lo = 0, hi = a.length - 1): void { if (lo >= hi) return; const p = partition(a, lo, hi); // p is the pivot's final index quicksort(a, lo, p - 1); // conquer the smaller elements quicksort(a, p + 1, hi); // conquer the larger elements }

A single partition over m elements does m-1 comparisons — each non-pivot element is compared once to the pivot. So the entire running time is governed by one quantity: the total number of pivot-versus-element comparisons across all recursive calls. Count those and you have analysed quicksort.

The two extremes: why the pivot is everything

Each partition splits an array of size m into pieces of size i and m-1-i, depending on the pivot's rank. The recursion tree's shape — and thus the total work — hangs entirely on that split.

Worst case (\Theta(n^2)): the pivot is always the smallest or largest element, so the split is 0 and m-1. The recursion is a degenerate chain of depth n, doing (n-1)+(n-2)+\dots+1 = \binom{n}{2} = \Theta(n^2) comparisons. T(n) = T(n-1) + \Theta(n). This is exactly what a sorted input does to a fixed first-element-pivot quicksort.
Best case (\Theta(n\log n)): the pivot is the median, so the split is even. T(n) = 2\,T(n/2) + \Theta(n), which the master theorem solves to \Theta(n\log n).

The picture below is the balanced recursion tree. Read it level by level: every level partitions a collection of subarrays whose sizes sum to n, so each level costs \Theta(n); and because balanced splits halve the size, there are only \log_2 n levels. Width times height: n \times \log n.

The genius of the average-case argument is that you need nowhere near a perfect median for this picture to hold up to constants. Even a wildly lopsided 1:9 split every time still gives depth \log_{10/9} n = \Theta(\log n). Only the truly pathological, near-total imbalance produces n^2 — and that is astronomically unlikely with random pivots.

The postcard proof: expected comparisons via indicators

Here is the argument every algorithms course builds toward. Rename the elements by rank: let z_1 < z_2 < \dots < z_n be the sorted order. Define the indicator

X_{ij} = \mathbf{1}\big[\,z_i \text{ and } z_j \text{ are ever directly compared}\,\big], \qquad i < j.

Two elements are compared only when one of them is chosen as pivot while both are still in the same subarray — quicksort never compares two elements twice. The total number of comparisons is X = \sum_{i < j} X_{ij}, and by linearity of expectation, \mathbb{E}[X] = \sum_{i < j}\Pr[z_i,z_j\text{ compared}].

Consider the set \{z_i, z_{i+1}, \dots, z_j\} of the j-i+1 elements between them (inclusive).
z_i and z_j are compared iff one of them is the first of this whole set to be chosen as a pivot. If any middle element z_\ell is picked first, it splits z_i and z_j into different subarrays and they never meet.
By symmetry each of the j-i+1 elements is equally likely to be picked first, so \Pr[z_i,z_j\text{ compared}] = \dfrac{2}{\,j-i+1\,}.

Now just sum. Substituting k = j - i:

\mathbb{E}[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1} \;=\; \sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{2}{k+1} \;<\; \sum_{i=1}^{n} 2H_n \;=\; 2nH_n \approx 2n\ln n.

And there it is: \mathbb{E}[X] = 2n\ln n + \Theta(n) = \Theta(n\log n). The same harmonic number H_n from the hiring problem, doing the heavy lifting again. Three lines, no recurrence, no master theorem — just indicators and linearity.

Why randomising the pivot fixes everything

The proof above quietly assumed a random pivot (each element equally likely to be picked first). With a fixed pivot rule — "always take the first element" — the 2n\ln n bound is an average over random input orderings, and a sorted input destroys it. Randomising the pivot moves the randomness from the input (which the adversary controls) to the coins (which they don't):

Pick each pivot uniformly at random from its subarray.
The expected number of comparisons is 2n\ln n = \Theta(n\log n) for every input — sorted, reversed, all-equal, adversarial, anything.
The worst case remains \Theta(n^2), but its probability is negligible and, critically, cannot be forced: no input is bad, only unlucky coin flips are.

This is the whole reason randomised quicksort is a Las Vegas algorithm — always correct, with a running time that is \Theta(n\log n) in expectation on any input at all. The single line "choose the pivot at random" converts a fragile average-case promise into a robust worst-case-input guarantee.

Both do \Theta(n\log n) comparisons, yet quicksort typically wins in wall-clock time. Two reasons, both about the machine rather than the maths. First, quicksort sorts in place with tiny constant overhead per comparison, while merge sort shuttles data through an auxiliary array, paying for extra memory traffic. Second, partitioning is exquisitely cache-friendly — it sweeps the array in two contiguous scans, exactly the access pattern modern memory hierarchies reward. The hidden constant in \Theta(\cdot), which asymptotic analysis deliberately discards, is where quicksort quietly banks its win. A reminder that \Theta is the beginning of a performance story, not the end.

A common muddle: students say randomised quicksort is \Theta(n\log n) "on average, so on a random input". That conflates two different randomisations. Deterministic quicksort's average is over random inputs — and a specific input (sorted) is genuinely, reliably terrible. Randomised quicksort's expectation is over the algorithm's own coins, and holds for a fixed, arbitrary input — there is no bad input, and re-running on the same array gives a fresh, independent draw. Also beware confusing "expected \Theta(n\log n)" with "\Theta(n\log n) with certainty": the worst case is still n^2; it is merely astronomically improbable. Expectation is a promise about the average of many runs, not a guarantee about any single one.