randomized quickselect

Randomized quickselect is the practical way to find the k-th smallest element: it is quicksort that only ever recurses into the half containing the answer, with the pivot chosen at random. Picking the pivot by a coin flip instead of a fixed rule is what makes its good behaviour depend on luck, not on the input — no particular arrangement of data can be its enemy.

The procedure: choose a pivot uniformly at random from the current array and partition in O(n). The pivot lands at its true rank p. If k equals p, return it; if k < p recurse left, else recurse right (only one side). With a random pivot, the expected size of the surviving side is a constant fraction of the current size, so the expected total work is the geometric series n + (3/4)n + (3/4)^2 n + ... = O(n). A clean way to see this: by linearity of expectation, summing the expected partition cost over all rounds is bounded by a constant times n. So the EXPECTED running time is O(n), where the expectation is over the algorithm's own random coin flips, for every fixed input.

This is the algorithm people actually use for medians, percentiles, and selecting good pivots, because its constant factor is tiny and its expected O(n) holds regardless of the input distribution — the randomness is internal, so there is no bad input, only at most a bad run. The crucial honesty: O(n) here is the EXPECTED time, not a worst-case guarantee. If the coin flips conspire to pick the smallest or largest element every time, you peel off one element per round and the running time is O(n^2). That worst case is astronomically unlikely (and an adversary cannot force it without seeing your coins), but it is not impossible — which is exactly the trade-off that median-of-medians removes at the cost of a bigger constant.