Randomized Quicksort and the Expected Comparison Count

Quicksort partitions an array around a pivot element, recursively sorts the two sides, and concatenates. Its worst case is quadratic, and the worst case is reached by the most ordinary input imaginable: an already sorted array partitioned on its first element. Randomizing the pivot choice does not remove the quadratic case, but it removes the input’s ability to select it. The cost becomes a random variable whose expectation is Θ(n log n) for every input, and the gap between the expectation and the observed cost of one run is the subject of the second half of the analysis.

The comparison bound as a sum over pairs

The cleanest derivation does not follow the recursion. It counts comparisons directly, using the fact that two elements are compared at most once: after they are separated by a partition, they never meet again in the same subproblem.

Label the elements by their rank in sorted order, z_1 < z_2 < ... < z_n, and let X_ij be the indicator that z_i and z_j are compared for some i < j. The total comparison count is sum over i<j of X_ij, so by linearity of expectation the expected count is the sum of the pairwise probabilities, with no independence needed.

Now determine when z_i and z_j are compared. They are compared exactly when the first element chosen as a pivot among the set {z_i, ..., z_j} is either z_i or z_j. If the first pivot from that set is some z_k strictly between them, the two elements fall on opposite sides of the partition and never meet. If it is z_i or z_j, they are compared directly at that partition and then separated forever.

In a uniformly random pivot choice, every element of a subproblem is equally likely to be the pivot first, so the first pivot drawn from the j - i + 1 elements of that rank interval is uniform over them. Hence

$$ \Pr[X_{ij} = 1] = \frac{2}{j - i + 1} $$

Summing over all pairs gives

$$ \sum_{i<j} \frac{2}{j-i+1} = 2\sum_{d=1}^{n-1} \frac{n-d}{d+1} < 2n \sum_{d=1}^{n-1} \frac{1}{d} \approx 2n \ln n $$

The harmonic sum is the source of the logarithm, and the constant is 2. For n = 1000 the bound is about 2 × 1000 × 6.9, or roughly 13,800 comparisons, against a lower bound of about 8,500 for any comparison sort by the information-theoretic argument. Randomized quicksort’s expected count is therefore within a factor of about 1.6 of optimal for large n, which is a stronger statement than “it is O(n log n)”.

The derivation also shows exactly where the randomness is used: in the claim that the first pivot among a rank interval is uniform over that interval. Any pivot rule with that property yields the same bound. Choosing the pivot uniformly from the subarray is the simplest such rule; choosing it as the median of three uniform samples also has the property in an approximate sense, with a different constant.

Median-of-three and the constant it changes

Taking the median of the first, middle, and last elements is a common refinement. It reduces the probability of a highly unbalanced split and improves the constant in the expected count, while keeping the pivot choice deterministic given the input. Determinism is the problem: an input constructed to make the median of those three positions a poor pivot defeats the rule, and such inputs are easy to construct for a known comparison function.

Randomizing the three sampled positions rather than their indices restores the guarantee. The pivot is then the median of three uniform draws from the subarray, which is not uniform over the subarray but is uniform over the input in the sense that no fixed input can force a bad choice. The expected split is better than the uniform-pivot case because the median of three concentrates around the middle. For a single uniform pivot the larger side has expected size 3n/4; for the median of three draws the pivot rank follows a distribution symmetric about the middle with the larger side averaging 11n/16. The gain is a reduction from 0.75n to about 0.69n, which is real but smaller than the extra comparisons suggest.

The cost is two extra comparisons to order three elements, plus the draws. Whether the improved split outweighs the extra work depends on the comparison cost. For integers compared in a register, the three-element ordering is cheap and the gain in split quality is real. For elements whose comparison invokes a user-supplied function with side effects or string collation, the extra comparisons are expensive and the uniform single draw is often preferable.

Recursion depth, stack space, and the tail call

Randomization bounds the expected number of comparisons, but it does not bound the recursion depth the same way. A split that puts n - 1 elements on one side recurses to depth n, and the expected depth of the recursion is Θ(log n) only if the recursion is written to recurse into the smaller side and iterate on the larger.

The standard formulation makes this explicit: after partitioning, recurse on the smaller subarray and loop on the larger one. The loop consumes no stack, so the stack depth is bounded by the logarithm of the original size, because each recursive call at most halves the problem. With this form the worst-case stack depth is O(log n) even when the splits are maximally unbalanced, and the quadratic time case no longer also exhausts the stack.

This is a case where the randomized analysis and the implementation detail interact. The comparison bound holds for any correct partition; the space bound holds only for the tail-recursive form. An implementation that recurses on both sides has an expected depth of Θ(log n) but a worst case of Θ(n), and an adversarial input that produces a bad split at every level is exactly the case randomization is supposed to make improbable rather than impossible.

What the expectation does not promise

The bound is over the random choices, for a fixed input. It says that if the same input were sorted many times with independent pivot draws, the average comparison count would be below 2n ln n plus lower-order terms. It says nothing about a single run, and the distribution has a tail: the probability that the count exceeds c n ln n for a constant c above 2 decays only as a negative power of n, so a single run on a large array can be several times the expectation with a probability small but not negligible.

Two consequences follow. First, a latency-sensitive sort cannot rely on the expected bound for its worst case: the quadratic outcome is possible for any input, and randomization only makes it improbable. Second, a test that asserts a comparison count below a threshold must use a threshold above the expectation with margin, or it will fail on legitimate runs.

The expected count is also not the expected running time. Comparisons are only part of the work; partitioning moves elements, and the movement pattern is what determines cache behaviour. A partition that scans two pointers from the ends has good locality for the scan but writes to two locations per step. The number of swaps is bounded by the number of elements, so the total movement is linear per level and Θ(n log n) overall, with a constant that depends on the fraction of elements that cross the pivot.

Duplicates break the rank argument

The derivation assumes distinct elements, because it labels them z_1 < ... < z_n and treats the rank interval as a set of j - i + 1 distinct elements. With duplicates, the strict ordering fails and the probability calculation changes.

The practical failure is sharper than the technical one. A two-way partition that places elements equal to the pivot on one side only, say the left, will put all duplicates on one side and produce a maximally unbalanced split. An array of n identical elements then partitions into n - 1 and 0 at every level, giving Θ(n^2) time with probability 1 regardless of pivot choice. Randomization cannot help, because every pivot is equally bad.

The fix is a three-way partition: elements less than the pivot, equal to the pivot, and greater than the pivot. The equal group is finished in one pass and is never recursed into. With this partition, an array of identical elements takes Θ(n) time, and the recursion handles only the strictly smaller and strictly larger groups. The comparison bound for the three-way variant is different, and the standard analysis of it is more delicate, but the duplicate case is the one that matters in practice because real keys collide.

A subtler variant of the same problem appears with many elements sharing few distinct values. A two-way partition does not degenerate to quadratic if the pivot is chosen uniformly and the duplicates are distributed on both sides, but the expected depth grows with the number of duplicates per value. Three-way partitioning removes the dependence entirely.

Choosing between randomized and deterministic selection

The same partition routine underlies quickselect, which finds the k-th smallest element in expected linear time. The analysis is a geometric-series argument rather than a pair sum: the expected work at each level shrinks geometrically because the pivot falls in the middle half with constant probability, so the total is Θ(n).

The deterministic alternative, median-of-medians, guarantees linear time by choosing a pivot that is provably within a constant fraction of the middle. It costs more per pivot selection and has a larger constant. In practice the randomized version is faster on typical inputs and the deterministic one is chosen when the worst case must be bounded, as in a library routine that cannot afford a quadratic tail on adversarial input.

The recursion in Randomized Recurrences and the Indicator Variable Method is where the quickselect argument gets its shape: the expected cost satisfies a recurrence over the random split point, and the solution technique is to bound the sum of the tail probabilities rather than to solve the recurrence directly. The pivot itself comes from a bounded draw, as described in Unbiased Random Integers from a Finite Random Source.