Chapter 9: Medians and Order Statistics

The simplest cases, finding the minimum or maximum, each require exactly n–1 comparisons, and finding both simultaneously can be done in only 3⌊n/2⌋ comparisons by processing elements in pairs and comparing each pair's smaller value to the running minimum and larger value to the running maximum. For the general selection problem, RANDOMIZED-SELECT mirrors quicksort's partitioning strategy but recurses into only one side: a random pivot is chosen, the array is partitioned around it, and if the pivot lands in the ith position it is returned immediately; otherwise the algorithm recurses left or right depending on whether i falls below or above the pivot's rank, achieving an expected running time of Θ(n) since a good pivot is found with probability at least one half. For applications requiring a worst-case guarantee, the deterministic SELECT algorithm achieves Θ(n) in all cases by carefully constructing a reliable pivot: it divides the input into groups of five, finds each group's median directly, recursively selects the median of those medians as the pivot, and partitions around it — ensuring that a constant fraction of elements is eliminated at every step, yielding the recurrence T(n) ≤ T(n/5) + T(7n/10) + Θ(n), which solves to Θ(n). While SELECT is theoretically optimal and input-agnostic, RANDOMIZED-SELECT is simpler and faster in practice, and together they establish that selection — unlike sorting — carries no Ω(n log n) lower bound in the comparison model.