linear-time selection

The selection problem asks for the k-th smallest element of an unsorted list — for example the median (the middle one), the minimum (k=1), or the 90th percentile. The obvious method is to sort everything and read off position k, which costs O(n log n). But finding one element should not need to fully order all the others, and indeed selection can be done in O(n) — linear time — which is asymptotically faster than any comparison sort.

The divide-and-conquer engine is partition, borrowed from quicksort. Pick a pivot and partition the array so smaller elements go left and larger go right; this puts the pivot at its true sorted index, say position p, in O(n). Now compare k with p: if k equals p you have found the answer; if k < p the k-th smallest lies in the left part, so recurse there; if k > p recurse in the right part for the adjusted rank. Crucially, you recurse on ONLY ONE side, not both — unlike quicksort. If each partition shrinks the array by a constant fraction, the work forms a geometric series n + (fraction)n + (fraction)^2 n + ... that sums to O(n). The two ways to guarantee a good pivot give two variants: median-of-medians (deterministic worst-case O(n)) and a random pivot (expected O(n)).

Linear-time selection is a striking result: you can extract the median, or any order statistic, without paying the full sorting price, because you discard one side at every step instead of processing both. It is used as a subroutine to pick good pivots, to find percentiles in statistics, and inside many geometric and optimization algorithms. The honest catch is the same recurring one: the deterministic O(n) (median-of-medians) hides a large constant, so the randomized expected-O(n) version is what people actually run, accepting that its worst case is O(n^2) on a freak run of unlucky pivots.