Finding the Median With Few Comparisons

The problem: you're handed a list of numbers and asked for the median — the middle value. The obvious move is to sort the whole list and read off the middle entry. An interviewer will then ask: do you really need to sort everything to find just one position in the sorted order? The answer is no, and the gap between "sort it all" and "just find the median" is exactly the kind of efficiency question quant interviews like to probe.

The technique: you don't need the full order, just one position

Sorting a list of $n$ numbers takes about $n \log n$ comparisons, because you're extracting the entire order — every item's rank relative to every other. But the median question only asks for one rank: the middle one. Selection algorithms like quickselect exploit this by picking a pivot, partitioning the list into "smaller" and "larger" halves (the same partition step as quicksort), and then — unlike quicksort — throwing away the half that can't contain the median and recursing only into the half that can. Each round does roughly $n$ comparisons but the list you recurse into shrinks by about half, giving an expected total of about $2n$ comparisons rather than $n \log n$.

Worked example 1: quickselect versus full sort at scale

Take $n = 1{,}000{,}000$ numbers. Full sort needs on the order of $n \log_2 n \approx 1{,}000{,}000 \times 20 = 20{,}000{,}000$ comparisons. Quickselect for the median needs on the order of $2n = 2{,}000{,}000$ comparisons in expectation — a 10x reduction, because you stopped paying to learn the order of numbers that were never going to be the median anyway. That saving is the entire point of the puzzle: identify what information the question actually needs before reaching for the tool that gives you more information than that.

Worked example 2: the classic "median of 5" comparison count

A tighter version of the puzzle: given exactly 5 numbers, what's the fewest pairwise comparisons needed to find the median? You can do it in 6. Compare them in two pairs first (2 comparisons), compare the two "winners" of those pairs against each other (1 comparison) to find the largest of the four compared so far and eliminate the smallest of that pair's loser, then carefully compare the fifth number against the survivors of a small decision tree. Working through the cases, every path resolves in at most 6 comparisons — well short of the roughly 8 a naive sort of 5 elements would use, and the reason interviewers ask this version is that it forces you to draw out a decision tree by hand rather than just quoting a big-$O$ formula.

What this means in practice

Any time a problem asks for one statistic derived from a sorted position — the median, the top decile cutoff, the k-th largest trade size in a session — reach for a selection algorithm, not a full sort, if the list is large and you only need that one number. In a live coding round this is also a signal to the interviewer that you distinguish "I need an ordering" from "I need one fact about an ordering," which is a habit that carries directly into production code where sorting a huge array just to read one entry is a wasted pass over the data.