Four other pages on this site already lean on this technique by name without ever building
it: KD-Tree and Ball Tree both mention finding a median in linear time
to keep their build step balanced, Minimum Bottleneck Spanning Tree
compares its own threshold-narrowing step to it directly, and Trapezoidal Map cites the same harmonic-series
argument it relies on. Quickselect finds the k-th smallest element of an unsorted
array — the minimum, the maximum, the median, any rank in between — without fully sorting
anything. It reuses quicksort's own partition step
exactly, unchanged, and gets from O(n log n) down to expected O(n) by
recursing into only one side instead of both. That makes it one of three entries in Searching that isn't really a search at all — alongside Ternary Search and Binary Search on Answer, it answers "which
value has this rank" rather than "does this value exist."
Enter an array, a target rank k (0-indexed — 0 is the
minimum, n-1 is the maximum), and a pivot strategy, then step through. Watch what
happens at each partition: the side that doesn't contain rank k fades out
immediately and is never touched again, unlike quicksort's bar chart, where both sides stay live
because quicksort has to finish sorting everything. Paste in 1,2,3,4,5,6,7,8,9,10,11,12
with k = 0 and pivot set to "last element" to see the same worst case
quicksort's own Pitfalls describes — here it's
worse in relative terms, since there's no other side's work to amortize it against.
Partitioning around a pivot does the same thing here as in quicksort: after the sweep, the
pivot sits at its true final rank p in the array — everything left of it is smaller,
everything right of it is larger. Quicksort recurses into both sides because it needs
every element sorted eventually. Quickselect only needs one element, at rank
k — and the partition itself already answers which side that is: if
k === p, the pivot is the answer and nothing else is examined again; if
k < p, rank k can only be among the smaller elements, and the larger
side is discarded outright, not "sorted later"; if k > p, the reverse. Nothing on
the discarded side can be the answer to a different question than the one being asked, so nothing
on it is ever worth another comparison.
That single-recursion difference is exactly what turns O(n log n) into expected
O(n). Quicksort pays a full O(n) partitioning pass at every one
of its O(log n) levels, because both halves need it. Quickselect pays a shrinking
partitioning pass — roughly n, then (with a decent pivot) roughly n/2,
then n/4, and so on — because only the surviving half is ever partitioned again. That
sequence n + n/2 + n/4 + ... < 2n is a geometric series, not a sum over
log n full-size levels, and it's the whole reason the two algorithms end up in
different complexity classes despite sharing the same partition code.
The partition function is identical to quicksort's own Lomuto
partition — copy it verbatim. The only change is the wrapper: one recursive call, chosen by
comparing k to the pivot's returned index, instead of two.
function partition(arr, lo, hi) {
const pivot = arr[hi];
let i = lo - 1;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
return i + 1;
}
function quickselect(arr, k, lo = 0, hi = arr.length - 1) {
if (lo === hi) return arr[lo];
const p = partition(arr, lo, hi);
if (k === p) return arr[p];
return k < p ? quickselect(arr, k, lo, p - 1) : quickselect(arr, k, p + 1, hi);
}Picking the pivot from a fixed position — always the last element, say — has the exact same adversary problem as quicksort: an already-sorted or reverse-sorted array makes every partition as lopsided as possible. Median-of-medians is a deterministic pivot-selection rule that guarantees worst-case linear time regardless of input order, at a real cost in constant factor. Split the range into groups of 5, find each group's median with a plain insertion sort (5 elements, cheap), then recursively select the median of those group-medians using this same algorithm — that median-of-medians value is provably not too extreme (worse than roughly 30% of the elements on either side, from how the groups are constructed), which caps how lopsided any one partition can be, however the input is arranged.
// select(arr, lo, hi, k): after this returns, arr[k] holds the k-th smallest of arr[lo..hi]
function select(arr, lo, hi, k) {
if (lo === hi) return arr[lo];
const pivotIdx = medianOfMediansPivotIndex(arr, lo, hi);
const p = partition(arr, lo, hi, pivotIdx);
if (k === p) return arr[p];
return k < p ? select(arr, lo, p - 1, k) : select(arr, p + 1, hi, k);
}
function medianOfMediansPivotIndex(arr, lo, hi) {
const n = hi - lo + 1;
if (n <= 5) {
insertionSort(arr, lo, hi);
return lo + Math.floor(n / 2);
}
let numMedians = 0;
for (let i = lo; i <= hi; i += 5) {
const groupHi = Math.min(i + 4, hi);
insertionSort(arr, i, groupHi);
const medianIdx = i + Math.floor((groupHi - i) / 2);
[arr[lo + numMedians], arr[medianIdx]] = [arr[medianIdx], arr[lo + numMedians]];
numMedians++;
}
// the recursive call below leaves the true median-of-medians sitting at this index
const target = lo + Math.floor(numMedians / 2);
select(arr, lo, lo + numMedians - 1, target);
return target;
}Verified from scratch against a sort-and-index oracle before trusting any of the numbers below:
4,320 exhaustive checks (every permutation of a 6-element array, every rank) and 20,000 randomized
checks (arrays up to 80 elements, random ranks), 0 mismatches. Then measured, not asserted, on the
exact adversarial input that breaks a fixed last-element pivot — an ascending array, searching for
the minimum (k = 0, the single worst rank for that pivot rule):
| n | median-of-medians | last-element pivot |
|---|---|---|
| 50 | 233 (4.7x n) | 1,225 (24.5x n) |
| 100 | 546 (5.5x n) | 4,950 (49.5x n) |
| 200 | 1,202 (6.0x n) | 19,900 (99.5x n) |
| 400 | 2,462 (6.2x n) | 79,800 (199.5x n) |
| 800 | 5,213 (6.5x n) | 319,600 (399.5x n) |
| 1,600 | 10,416 (6.5x n) | 1,279,200 (799.5x n) |
The n-multiple column is the whole point: median-of-medians holds flat around
5-6x n no matter how large n gets — genuinely linear, on the exact input
engineered to be worst-case for the alternative. The last-element column's own multiple doubles
every time n doubles, which is what quadratic growth looks like in a ratio-to-n
column rather than a raw total. The trade is real, though: on random (non-adversarial)
input, median-of-medians costs more than a plain random-pivot quickselect for the same rank — its
own grouping and recursive-median overhead is paid on every input, good or bad, which is exactly
why general-purpose libraries default to a random or median-of-three pivot and only reach for a
median-of-medians-style fallback (as C++'s std::nth_element does, in an
"introselect" pattern mirroring introsort) when a
guaranteed bound actually matters more than the common case.
A fixed-position pivot on already-ordered data is quadratic, and it's worse here than
in quicksort, not better. The numbers above show it precisely: an ascending array of size
n = 400 searching for its own minimum with a last-element pivot costs 79,800
comparisons — exactly n(n-1)/2, confirmed exactly at every size tested from 50 to
1,600. The reason it's worse in relative terms than quicksort's own worst case (which is
also O(n²)) is that quicksort's lopsided partitions at least make progress toward a
fully sorted array either way; quickselect's only payoff is the one target rank, so the entire
cost buys nothing extra. Switching only the pivot strategy fixes it without touching anything else: a
random pivot on the identical adversarial array, same target rank, averages
around 1,323 comparisons at n = 400 across repeated draws (individual runs ranged
from roughly 400 to 1,500 in a 20-trial sample) — nowhere near 79,800, because the bad case now
depends on unlucky random draws rather than on the data, and this particular data no longer forces
one every single time. Try it live: load the ascending array with "last element," then switch the
dropdown to "random" and reload the same array and rank — the exact comparison count in the table
below will vary run to run, but it never comes close to the last-element column's number.
Recursing into both sides, out of habit from quicksort, silently turns
O(n) into O(n log n) — it still returns the right answer, just slower,
with no error to catch it. If k < p, the elements at and after rank
p genuinely cannot be the answer to "what is rank k," so a second
recursive call into [p+1, hi] does real work that's thrown away — every comparison in
it is spent confirming ranks nobody asked about. Measured against the correct single-recursion
version on the same random arrays and target ranks: the gap starts small (1.7x more comparisons at
n = 50) and widens as n grows (2.4x at n = 200, 3.1x at
n = 800) — exactly the signature of two different complexity classes diverging, not a
fixed constant-factor mistake. Because the output is still correct, this bug survives ordinary
testing; only a comparison count (or a complexity argument) catches it.
Time: O(n) expected with a random or median-of-three pivot — the
geometric-series argument above. Worst case is O(n²) with any fixed
pivot rule on adversarial input, or a guaranteed O(n) using median-of-medians, at
roughly double the constant factor of the average case (see the measured table above).
Space: O(1) beyond the recursion stack for the simple version —
partitioning happens in place, and only one side is ever recursed into, so (unlike quicksort) the
stack depth is expected O(log n) too, not just the partitioning work.
See Choosing a Search Algorithm for how this fits alongside the site's other ten Searching entries.