The selection problem, and why not just sort
Here is a deceptively plain question: given an unsorted array of n numbers and a rank k, find the k-th smallest element. The median is the famous special case (k = n/2), but k could be anything — the 7th smallest, the 90th percentile. The lazy answer is sort the whole array and read off position k. That works, but sorting costs Theta(n log n), and it does far more than we asked: it puts every element in order when we only wanted one of them in its place. The goal of this guide is to do the job in honest linear time, O(n) — faster than any sorting-based approach can ever be.
Why should O(n) even be possible? Because finding one ranked element is genuinely easier than full sorting. We do not need the relative order of all the small elements among themselves, nor of all the large ones — we only need to know how many are smaller than the answer, and to isolate the one that sits at rank k. That is a lot less information, and the algorithms below buy speed by refusing to compute the order we will never use.
Quickselect: partition, then recurse into one side
The starting point is the partition routine you already met in the quicksort guide. Pick a pivot, then rearrange the array so everything smaller than the pivot sits to its left and everything larger to its right; the partition step leaves the pivot in its final sorted position, say index p. Now comes the twist that makes selection cheaper than sorting. Compare p with the target rank k: if p equals k, the pivot is the answer and we stop. If k < p, the answer lies entirely in the left piece, so we recurse only there; if k > p, it lies in the right piece, and we recurse only there. We throw one whole side away every time.
This is quickselect, and it is a beautiful example of decrease and conquer: unlike merge sort or full quicksort, which recurse into both halves, here only one recursive call survives — exactly like binary search, but on unsorted data with a partition doing the splitting. When the pivot lands near the middle, the surviving piece is roughly half the size, so the work per level shrinks geometrically: n, then n/2, then n/4, and so on. That geometric series sums to about 2n, which is O(n). One good split after another, and selection is linear.
Two ways to tame the pivot
There are two routes out of the quadratic worst case. The first is to give up on guaranteeing a good pivot and instead pick one at random every time. This is randomized quickselect, and a short analysis shows its expected running time is O(n): on average a random pivot lands far enough from the ends that the surviving side shrinks by a constant fraction. It is simple, fast in practice, and almost always what real libraries use. But be precise about the claim — O(n) here is the expected time over the coin flips. There is still a vanishingly unlucky run of pivots that drives it to O(n^2); randomness moves the bad case off any fixed input, it does not abolish the bad case.
The second route is more ambitious: build a pivot that is provably decent, with no coin flips and no escape hatch — a deterministic O(n) algorithm whose worst case is linear. The catch is circular: a perfect pivot would be the median, but the median is exactly the hard thing we are trying to find. The escape from that circle is the central idea of this guide, and it has a memorable name.
Median of medians: a pivot you can trust
The median-of-medians trick finds an approximate median fast, and an approximate median is all a pivot really needs. The recipe is concrete and a little surprising the first time you see it.
- Split the n elements into groups of 5 (the last group may be smaller) — about n/5 groups in all.
- Find the median of each tiny group of 5. Each costs only constant time, since a group of 5 is sorted with a fixed handful of comparisons, so all the group-medians together cost O(n).
- Collect those about n/5 group-medians into a new list, and find the median of THAT list — recursively, by calling this same selection algorithm on a problem of size n/5.
- Use that median-of-medians as the pivot, partition the original array around it, and recurse into the one surviving side exactly as quickselect does.
Why is this pivot good? Picture the group-medians, and let M be the median among them — our chosen pivot. Of the n/5 group-medians, half are at most M. For each such group, its median is at most M, and the two elements below that median within its group of 5 are also at most M. So each of those groups contributes 3 elements guaranteed to be at most M. That is roughly 3 elements from about half of the n/5 groups — about (3/10)n elements that are no larger than the pivot. By the mirror-image argument, at least about (3/10)n elements are no smaller than the pivot. The pivot is therefore never extreme: at least 3 out of every 10 elements sit on each side of it.
That guarantee is the whole point. Since at least about 3/10 of the elements lie on each side, the side we recurse into can hold at most about 7/10 of the elements. The surviving piece always shrinks by a constant factor — never just by one, the way the careless pivot allowed. The bad case that wrecked plain quickselect simply cannot occur, because we engineered the pivot so it cannot.
Why the recurrence comes out linear
Now count the cost honestly. Each call does O(n) work outside recursion — splitting into groups, finding the small medians, partitioning. Then it makes two recursive calls: one of size n/5 to find the median of the group-medians, and one of size at most 7n/10 to recurse into the surviving side. Writing that down gives the recurrence below. The astonishing thing is that this two-call recurrence still solves to O(n).
T(n) = T(n/5) + T(7n/10) + O(n) key fact: 1/5 + 7/10 = 2/10 + 7/10 = 9/10 < 1 so: T(n) <= c*n * (1 + 9/10 + (9/10)^2 + ...) = c*n * 10 = O(n)
Read the recurrence with the recursion-tree habit from earlier in this rung. The root does c*n work. Its two children handle sizes n/5 and 7n/10, so the next level does c*(n/5) + c*(7n/10) = c*(9n/10) work — only 9/10 as much as the level above. Every level is 9/10 of the one before, so the total is a shrinking geometric series c*n*(1 + 9/10 + 81/100 + ...), which sums to at most 10*c*n. The decisive fact is 1/5 + 7/10 = 9/10 < 1: the two subproblems together are strictly smaller than the original, so the work decays geometrically instead of staying flat across levels (which is what made merge sort's tree cost n per level and land at n log n).
Which one should you actually use
Here is the honest practitioner's verdict. Median-of-medians is a landmark theoretical result: it proves that deterministic, worst-case linear-time selection is possible at all, which is a genuinely surprising fact and a model of how clever pivot design beats a naive bound. But its hidden constant is large — all that grouping, sub-median finding, and the extra recursive call mean its O(n) carries a heavy coefficient. In practice randomized quickselect is simpler and faster, and the asymptotic O(n) of median-of-medians hides a constant big enough that the randomized method usually wins on real inputs. Median-of-medians earns its keep as a fallback: some libraries run randomized quickselect and switch to median-of-medians only if the recursion runs too deep, getting fast typical behavior with a worst-case linear guarantee.
Step back and see the bigger lesson of this whole rung. Across binary search, merge sort, quicksort, Karatsuba, and now selection, the entire game has been the same: a problem of size n, a way to split it, and a fight to keep the combined cost low enough that the recurrence collapses to something small. Selection is the purest illustration — we did not just split cleverly, we manufactured the very pivot that makes the split safe, turning a fragile O(n)-or-O(n^2) gamble into an ironclad O(n). That move — engineer your subproblem so the worst case cannot bite — is one of the most powerful ideas you carry forward out of divide and conquer.