Motivation
Quicksort chooses a pivot, partitions the other items around it, and recursively sorts the two sides. A badly chosen pivot at every stage produces quadratic work. Randomizing pivot choices does not rule out that execution, but it makes it possible to quantify its average cost over the algorithm's own choices for every fixed input.
Rather than solving a recurrence directly, we ask a more local question: for two items of known sorted ranks, what is the probability that they are ever compared? Summing those probabilities gives an exact expected comparison count. The proof also shows why independence between pair-comparison events is unnecessary.
Definitions
Definition 1.9.1
(Pair indicators and the comparison count)
The input consists of distinct keys in a comparison model. At each recursive call containing keys, choose one pivot uniformly at random from those keys, independently of past random choices conditional on the current subproblem. Compare every other key in that subproblem once with the pivot, put smaller keys on one side and larger keys on the other, and recursively sort the sides. Calls of size zero or one make no comparisons.
Let the sorted keys be . For each , let be one if and are compared during the execution and zero otherwise. Let be the total number of key comparisons made by the stated partition rule. Write for and .
Theorem 1.9.2
(Pair comparison probability)
For every pair , the probability that and are compared is .
Theorem 1.9.3
(Exact expected comparison count)
For , randomized quicksort makes
expected key comparisons, interpreting . In particular the expectation is .
Proof: which pivot separates a pair?
Proof
(Only the first pivot in an interval matters)
Consider the interval of sorted ranks . Before any key from this interval is chosen as a pivot, all keys in the interval remain together in one recursive subproblem. A pivot of smaller rank sends the whole interval to its greater side; a pivot of larger rank sends the whole interval to its smaller side. Thus neither endpoint can be separated from the other by an outside pivot.
When the first pivot from the interval is chosen, there are two possibilities. If it is or , the other endpoint is in the same subproblem and is compared with that pivot. If it is an interior key, the two endpoints go to opposite recursive subproblems and can never be compared later. Any particular pair can be compared at most once, because after one endpoint is chosen as pivot it leaves the recursive calls.
The first chosen pivot from the interval is uniformly distributed among its keys. One way to see this is to assign the keys a uniformly random priority order in advance and always use the smallest-priority key in a subproblem as pivot. The induced pivot is uniform in each current subproblem, and the first priority among any fixed subset is equally likely to belong to any member. Equivalently, conditioning on outside pivots repeatedly preserves symmetry among the interval's keys. Exactly two interval keys are endpoints, so the desired probability is .
Proof X-ray
The first pivot in an interval
Pivots outside the rank interval keep both endpoints together. An endpoint pivot makes their one comparison; an interior pivot separates them permanently. Uniform symmetry among interval keys therefore reduces the probability calculation to two favorable keys out of the interval size.
Proof: summing the indicators
Proof
(Summing the pair probabilities)
Every comparison is between a pivot and one other key, and no pair is compared twice. Hence . By linearity of expectation, which does not require the indicators to be independent,
For interval length , there are pairs with that interval length. Therefore, for ,
For both sides are zero by convention. The integral bound for gives the asymptotic upper bound. The harmonic sum also grows at least on the order of , so the expected comparison count is for sufficiently large .
Correctness and cost model
For each recursive call, every key placed left of the pivot is smaller and every key placed right is larger. The two recursive results are sorted by induction on subproblem size; concatenating the sorted left side, pivot and sorted right side gives all input keys in order. Each call removes its pivot from further recursion, so the algorithm terminates for every pivot sequence.
The exact theorem counts key comparisons under the stated partition procedure. If partitioning performs constant additional work per examined key and the pivot can be sampled in constant time, total expected running time is under that model. A concrete implementation must account for its own pivot-generation cost and storage. The expectation is over random pivot choices on a fixed input; it does not assume the input itself is randomly ordered.
The worst possible pivot sequence repeatedly picks the minimum or maximum. It makes comparisons. The probability of an unfavorable run may be small, but an expected bound does not prohibit it.
Concept lensStructural
The recursion tree is a random binary search tree
Record each pivot as the root of its subproblem, with the pivots of its two sides as children. This is a binary search tree on , and a key is compared once with each pivot above it. So exactly when one of is an ancestor of the other, and is the sum of all node depths, with the root at depth zero. The expectation above is the expected total depth; for it is .
Worked examples
Worked example 1.9.4
(Two keys)
For , whichever key becomes pivot is compared with the other exactly once. The formula gives , agreeing with the direct count.
Worked example 1.9.5
(Three keys)
For , the median is chosen first with probability , producing two comparisons and no further comparisons. An endpoint is chosen first with probability , producing two comparisons and then one comparison between the remaining keys. The expectation is . The formula gives .
Worked example 1.9.6
(An endpoint pair)
The smallest and largest among five sorted keys are compared only if one of those two is the first pivot among all five. Their comparison probability is . A middle pivot separates them immediately.
Worked example 1.9.7
(A worst-case execution)
For five keys, suppose the smallest remaining key is chosen at each nontrivial call. The partition comparisons are . This is a possible execution of the randomized procedure, even though its expected count is smaller.
Common mistakes
Counterexample mode
Expected does not mean every run
On three keys, choosing an endpoint first produces three comparisons, while choosing the median first produces two. The expected count is , which is neither a bound on each execution nor the count of an actual execution.
Common mistake
(Treating the comparison indicators as independent)
The comparison indicators are generally dependent. If an interior pivot separates a pair, it also affects which other pairs can later be compared. The sum of their expectations remains valid without any independence assumption.
Common mistake
(Averaging over inputs instead of pivots)
The expectation is over the algorithm's pivot choices, not over inputs. A deterministic rule such as always taking the first key as pivot makes comparisons on an already sorted input, because each pivot is the minimum of its subproblem. The bound holds for every fixed input precisely because only the pivots are random.
Counterexample mode
Equal keys break the exact formula
Suppose the keys are not distinct and the partition rule sends every key that is not larger than the pivot to the left side. Take equal keys. Whichever key is the pivot, the other two are compared with it and both go left; the left side of size two costs one more comparison. Every run makes exactly comparisons, while the distinct-key formula gives . The pair probability no longer applies because no key is ever strictly smaller than another. The repair is to assume distinct keys, or to analyze the specific tie rule separately; attaching tie-breaking identifiers helps only if the comparisons actually use them. Two-way and three-way implementations treat duplicates differently, so their exact counts need separate analysis.
Why the random-priority view is valid
A uniformly random permutation of all keys can be viewed as assigning each key a unique priority. The first priority in any nonempty set is equally likely to be any key in that set. After a pivot is exposed, the relative priority order of the remaining keys is still uniformly random. Restricting that order to either recursive side gives the same conditional distribution as fresh uniform pivot choices in that side.
This coupling is a proof device, not a requirement that an implementation generate a full permutation. It lets us discuss the first pivot among the rank interval even if outside pivots are selected earlier. The earliest-priority member of the interval is uniform among its members, and before it appears every outside pivot keeps the interval together.
The exact count depends on the rule that each nonpivot key is compared once with its pivot. Partition implementations can make extra key comparisons, for example when performing certain boundary checks. They can still be analyzed using similar ideas, but the displayed equality should not be copied unchanged without checking the actual comparison rule.
An explicit four-key calculation
With four keys, there are three adjacent-rank pairs. Each is necessarily compared: no interior key can separate adjacent ranks, and the first pivot among the pair must be one endpoint. There are two pairs whose rank interval has length three, each compared with probability , and one pair whose interval has length four, compared with probability . Summing gives
The harmonic formula gives the same number because and . This calculation counts pair events, not independent coin flips. Some comparisons can occur together, and the value need not be the number of comparisons in any particular run.
How rare is the most unbalanced sequence?
For , a maximum-comparison execution chooses either the smallest or the largest key in every subproblem of size at least two. In a call of size , either extreme is chosen with probability . Given that all previous choices were extreme, the only remaining nontrivial call has size . Multiplying the conditional probabilities gives
For this probability is one; for it is , matching the direct example. Conversely, a non-extreme pivot creates two nonempty sides and reduces the maximum possible number of later comparisons below that of a single remaining subproblem. Thus the event described is exactly the maximum-count event for distinct keys under this partition rule. It is possible for every finite even though the probability decreases rapidly.
Two sides of the harmonic estimate
For , follows by comparing each reciprocal for with the integral of over . For a lower bound, group terms in blocks: the terms from through each have value at least , and there are of them. Each complete block therefore contributes at least one half. The number of complete blocks up to grows proportionally to .
Substituting these bounds into the exact formula explains the asymptotic growth. The negative linear term does not change the order: for sufficiently large , the harmonic factor exceeds a fixed positive constant by an amount growing like . The exact expression is more informative for small inputs, where asymptotic notation hides substantial differences.
The pair probabilities depend on ranks and interval lengths rather than on the input's original arrangement. Under uniform pivot selection and this comparison rule, every fixed permutation of the same distinct keys has the same expected count. This symmetry is a property of the randomized algorithm, not a promise that real-world inputs arrive uniformly at random.
Summary
Two keys are compared exactly when one is the earliest pivot among the keys between their ranks. That happens with probability . Summing pair indicators yields the exact expectation and its growth, while individual executions can remain quadratic.
Exercises
Quick check
(Compute the probability that ranks and are compared.)
Solution · Answer
Their rank interval has length three, so the probability is . They are compared if rank or rank is the first pivot among ranks .
Quick check
(For four keys, what is the maximum possible number of comparisons under the stated rule?)
Solution · Answer
Repeatedly selecting an extreme key gives comparisons. No execution can exceed this. The first call makes three comparisons and leaves three keys on its two sides. If all three stay on one side, they cost at most more comparisons; a split into sides of sizes two and one costs at most . Hence the total is at most .
Quick check
(Why can two keys be compared at most once?)
Solution · Answer
A comparison occurs when one member of the pair is selected as pivot. That pivot does not appear in any later recursive call, so the pair cannot be compared again.
Quick check
(Explain why linearity of expectation applies even though the indicators may be dependent.)
Solution · Answer
For a finite sum, expectation distributes over addition regardless of dependence: . Independence would be relevant to some product calculations, but is not needed here.