Why is quickselect cheaper than fully sorting when you only need the k-th smallest value?

## The question selection actually answers An *order statistic* is the value that would sit at a given position if the data were sorted: the minimum is the 1st order statistic, the median is the middle one, and a p99 latency is the order statistic at index `0.99 * n`. Nothing in that definition requires the data to actually *be* sorted. It only requires you to know which value would land at that one index. Full sorting answers a much bigger question than that. It fixes the position of every element, which is `n` answers when you asked for one. The comparison-sort lower bound of Omega(n log n) applies to producing that total order; it does not apply to producing a single order statistic, and selection is exactly the algorithm that exploits the gap. ## The mechanism: partition, then discard A partition step picks a pivot value and rearranges the range so that everything smaller sits to its left, everything larger to its right, and the pivot itself sits at some index `p`. The crucial property is that `p` is the pivot's **final** index in the fully sorted order, established by a single linear scan and without sorting either side. That one fact splits the two algorithms apart: - **Sorting** must recurse into the left range and the right range, because it owes an answer for every index. - **Selection** compares the wanted index `k` against `p`. If `k == p`, the pivot is the answer and the algorithm stops. If `k < p`, the answer lies strictly to the left and the entire right side, however large, is never looked at again. If `k > p`, symmetrically. So each round does linear work over a range and then commits to one sub-range. ## Why the discarding makes it linear Suppose each partition splits the range roughly in half. The first pass scans `n` elements, the second about `n/2`, the third about `n/4`, and so on. The total is the geometric series `n + n/2 + n/4 + ... < 2n`. The work is dominated by the very first pass; everything after it is a rapidly vanishing tail. That is the whole reason selection is linear in expectation. Contrast this with sorting, where the same halving happens but *both* halves are processed at every level. Each level then costs about `n` in total, there are about `log n` levels, and the sum is `n log n`. One recursive call instead of two is the entire difference between `2n` and `n log n`. | Goal | Typical cost | Extra space | Leaves data | | --- | --- | --- | --- | | One order statistic by selection | expected O(n) | O(1) with an iterative loop | reordered, partially partitioned | | Full order by comparison sorting | O(n log n) | depends on the algorithm | fully sorted | ## What the linear bound does and does not promise The expected-linear claim is an average over pivot quality, not a guarantee. If pivots repeatedly land near an end of the range, each round removes only a handful of elements and the total degrades toward O(n^2). Randomizing the pivot makes that outcome unlikely rather than impossible, and it is the single most important qualifier to attach whenever you say "selection is linear". The second thing the bound does not promise is a tidy result. After selection returns, the input has been rearranged in place: elements before index `k` are all no greater than the answer and elements after it are all no smaller, but neither side is sorted. If the caller still needs the original order, the sample has to be copied first, and that copy is real memory on a 10^8-element job. ## When sorting wins anyway Selection wins when you want a small, fixed number of positions out of a large collection. It stops winning when you want many of them: asking for a hundred different percentiles is a hundred linear passes, and one `n log n` sort answers every percentile request, past and future, from a single array. Sorting also wins when you need the neighbours of the answer, a sorted export, or a stable, reproducible ordering for downstream consumers. The decision is not "selection is faster", it is "how many of the n answers do I actually need".