Motivation
Selecting the th smallest item does not require sorting every item. A partition around a pivot tells us which side contains the desired rank, so only one side needs further search. An unlucky pivot can still make ordinary quickselect take quadratic time. The median-of-medians method spends additional work choosing a pivot that discards a constant fraction of the input in every large recursive call.
We prove a worst-case bound for distinct items in a comparison model. The constants in the proof are deliberately loose; the key point is that the two recursive subproblem sizes add to less than the original size by a linear margin.
Definitions
Definition 1.10.1
(Rank selection and lower median)
The input is a list of distinct totally ordered items and a rank with . The item of rank is the one with exactly smaller items in the list. The lower median of distinct items is the item of rank .
For , sort the list directly and return its th item. For larger , divide the list into groups of five, except possibly one smaller group. Sort each group and retain its lower median. Recursively select the lower median of these group medians.
Partition the original list into items smaller than , the pivot , and items greater than . If equals one plus the size of the smaller part, return . Otherwise recurse on the relevant part, adjusting after discarding the smaller part and the pivot. Distinctness makes the three parts unambiguous; handling duplicates requires a separate equal-key partition and rank check.
Theorems
Theorem 1.10.2
(Pivot discard bound)
For , at least original items are at least the pivot and at least are at most the pivot. Hence either strict partition has size at most .
Theorem 1.10.3
(Correctness and linear worst-case work)
The algorithm returns the item of rank . For fixed-size group sorting and linear-time partitioning, its worst-case comparison count is .
Proof sketch or proof idea
Proof
(Counting items on each side of the pivot)
At least group medians are at least the median pivot, counting the pivot, and at least are at most it. At most one group is incomplete. Every full group whose median is at least contains at least three items at least ; these groups are disjoint. Thus at least items are at least . The same argument applied to the other side gives the lower-side bound. This count includes the pivot, which is sufficient: the strict smaller part excludes all items at least , and similarly for the strict greater part.
Proof
(Correctness and the linear recurrence)
For correctness, partitioning gives the pivot's exact rank within the current list. If the target rank equals that rank the pivot is the answer. Otherwise, all items on the discarded side and the pivot are known to lie on the same side of the target. Recursing on the remaining list with its corresponding rank preserves the desired item. The subproblem shrinks, and the fixed-size base case is sorted correctly, proving correctness by induction on list size.
Sorting each group costs constant work because its size is at most five; there are groups, and partitioning is . Let be the worst comparison count over all valid input sizes at most , so it is nondecreasing. Thus for a constant and ,
The first recursive call chooses the pivot and the second is an upper bound on the one partition explored. For an induction bound , the sum of recursive sizes is at most . For , ; choose and large enough to cover the finitely many base sizes. Then . The induction proves .
Proof X-ray
Two recursive calls, but only one partition
Each term of the recurrence has one source. is the call that selects the pivot from the group medians. is the single partition explored afterwards, not both partitions, because the target lies on at most one side. Group size five supplies the fraction , and the pivot discard bound supplies . Their sum is , and this gap of about a tenth of is what pays for the linear work and for the additive once . The key move is to apply the induction hypothesis to both sizes at once, as .
Remove an ingredient and the argument fails. With groups of three the two fractions would be about and , summing to about , which leaves no gap to absorb . The proof therefore uses the specific fractions, not merely the existence of two smaller calls.
Worked examples
Worked example 1.10.4
(The rank update)
Suppose a partition of nine distinct items has four below pivot and four above it. The pivot has rank five. To select rank seven, discard the four smaller items and ; the desired item has rank among the four larger items.
Worked example 1.10.5
(A group median certificate)
For a sorted group , the median is . If the pivot is at most , the three group items are at least the pivot. If the pivot is at least , the three items are at most it. This local fact is counted over disjoint full groups in the proof.
Worked example 1.10.6
(Why an endpoint pivot is risky)
If quickselect always chooses the smallest item and seeks the maximum, it discards only one item at each step. Partition work sums as . The median-of-medians bound rules out this persistent imbalance for large calls.
Common mistakes
Counterexample mode
Choosing the median of medians is not choosing the true median
A tempting claim is that the pivot is the median of the whole list. Take in the groups , and . The group medians are , so the median of medians is , whereas the true median of the fifteen numbers is . This small list would use the base case in the stated implementation; the illustration isolates the pivot construction. The proof therefore does not assume exact middle rank. It requires only the weaker guarantee that the pivot leaves at least items on each side.
Common mistake
(Counting the incomplete group)
The incomplete group can contain fewer than three items on one side of its median, so it must be excluded from the three-per-group count when necessary. This is why the bound subtracts one group, giving rather than .
Common mistake
(Fearing two recursive calls)
A recurrence with two recursive calls is not automatically superlinear. Here their sizes have sum at most , leaving room to absorb the linear work. The argument would fail only if the size sum reached .
Where the rank bounds come from
The proof counts groups, not individual comparisons performed while finding the pivot. The list is split into disjoint groups, so the three certified elements from one group cannot also be counted as elements of a different group. When a full group median is at least , the median and the two elements above it are all at least . When its median is at most , the median and the two elements below it are all at most . We count each side separately; an element such as the pivot can contribute to both non-strict counts, which is harmless because each count bounds a different strict partition.
There are medians, including a representative for a possible short final group. A lower median of these representatives has at least half of them at most it and at least half at least it, even when is even. At most one certified group on either side may be short, so subtracting one full group gives the safe lower bound. The estimate sacrifices some valid elements, but the linear-time proof needs only a constant fraction, not the best possible additive constant.
The pivot itself is one of the original items. In an implementation, after it is found it may be moved or copied into a separate variable, but the partition must still account for it exactly once. If items are strictly smaller, the pivot has rank . When , the smaller items and pivot are discarded, leaving target rank in the larger part. Since , that new rank is within the larger part. When , the original rank is already valid in the smaller part.
Why the recurrence closes
The pivot-selection call has at most items. The selected partition has at most items. Their sum is therefore at most . The additive four is not ignored: for , the saved tenth of exceeds it by at least . Choosing an induction constant large enough to pay for the linear nonrecursive work then closes the estimate. The finitely many smaller inputs are covered by enlarging the same constant.
The proof defines as the worst cost over inputs of size at most , making it nondecreasing. This permits a recursive call of unknown size to be bounded by evaluated at a size upper bound. If were defined only for exactly items, monotonicity would need its own justification. Defining the monotone envelope makes the inequality explicit and does not weaken the final upper bound for any particular input.
The recurrence is a worst-case inequality rather than an exact equation. A pivot may return immediately, the selected partition may be smaller than the bound, and individual group sorts may use fewer comparisons. For an upper bound we charge a fixed linear amount for every call's grouping, sorting and partitioning. The proof does not claim that every execution takes exactly comparisons or that the constants are competitive with practical randomized selection.
Comparison model and a lower bound
The theorem counts comparisons between items and treats moving or indexing an item as constant work. The fixed-size base case can use any correct sorting method; because it handles fewer than one hundred items, its worst cost is bounded by an absolute constant. If comparisons themselves are expensive, the cost of each comparison must be included separately. Memory use and data movement are also separate resources: this proof is a comparison-count and linear-work upper bound under the stated model.
Finding the maximum illustrates why linear work is a natural target. In a comparison model, every item other than the maximum must lose at least one comparison; otherwise an item that has never lost could still be the maximum under a total order consistent with the observed outcomes. Each comparison has at most one loser, so at least comparisons are necessary in the worst case. The selection algorithm's bound is therefore asymptotically optimal for the maximum-selection instance. This argument does not require sorting the whole list.
Duplicate keys and model boundaries
The distinctness assumption lets the pivot stand alone. With duplicate keys, a correct adaptation partitions into less-than, equal-to and greater-than regions. If the desired rank falls inside the equal region, return the common key; otherwise recurse on one strict side with an adjusted rank. A complete proof must revise the counting and partition arguments to account for equal elements. This unit states the distinct-item theorem rather than silently relying on a two-way partition that can repeatedly retain many equal keys.
Counterexample mode
Duplicates break the distinct-item algorithm
A tempting claim is that the algorithm works unchanged when keys repeat. Take copies of the same key and . The pivot is that key, so no item is strictly smaller or strictly greater: both strict parts are empty, the rank is not , and there is no part left in which to recurse. The three-way repair partitions into less-than, equal-to and greater-than regions and returns the common key when the rank falls inside the equal region.
The fixed groups of five also matter to the arithmetic. Replacing five by another size changes both the pivot-selection call and the guaranteed discard fraction. One cannot copy the inequality without recomputing those quantities. The general strategy is broader than this particular choice, but the concrete proof belongs to the stated grouping and cost model.
Summary
A pivot of controlled rank permits one partition to be discarded. Grouping by five gives a constant-fraction guarantee, while recursive selection of the pivot costs another smaller call. The two size bounds and linear partition work yield a linear worst-case comparison count.
Exercises
Quick check
(A pivot has seven items below it. What is its rank?)
Count the pivot itself.
Solution · Answer
Its rank is eight: seven smaller items precede it.
Quick check
(If the desired rank is ten and the pivot has rank eight, what rank is sought among larger items?)
Count how many items are discarded.
Solution · Answer
The target is the second smallest among items larger than the pivot, since eight items including the pivot have been discarded.
Quick check
(Why can at most one group be incomplete?)
Think of how the list is cut into groups.
Solution · Answer
Divide the list consecutively into groups of five; only the final group can have fewer than five items.
Quick check
(Why is sorting every group still linear work?)
Count both the cost per group and the number of groups.
Solution · Answer
Each group has at most five items, so sorting one takes a fixed number of comparisons. There are groups.