Medians and Order Statistics: Quickselect

Finding the median return in a dataset, or the 95th-percentile latency in a set of measurements, is the selection problem: find the $k$-th smallest element of $n$ unordered elements. The obvious approach — sort everything, then read off index $k$ — costs $\Theta(n\log n)$, but selection is a strictly easier problem than full sorting, and this note shows it can be solved in expected linear time by reusing quicksort's partition subroutine in a new way: quickselect. It closes with a pointer to a worst-case-linear algorithm (median-of-medians) for when the expected-time guarantee is not enough.