Quickselect and order statistics

What this chapter covers

Sometimes you don't need the whole sorted order — you need one element of it: the median, the 95th percentile, the tenth-largest, the threshold for the top-k. Sorting gives you the answer, but it does far more work than the question requires. Quickselect finds the k-th smallest element in O(n) average time without sorting, by taking quicksort's partition and recursing into only the one side that can contain the answer. It's the elegant capstone of the recursion-and-sorting tier: the same machinery as quicksort, doing less work to answer a narrower question.

A bit of history

Quickselect is Tony Hoare's other 1961 algorithm. Having invented quicksort, he realized the same partition step could find an order statistic without the full sort, and published it as FIND the same year — so quickselect and quicksort are twins, born together. Hoare's version is O(n) on average but O(n²) in the worst case, inheriting quicksort's bad-pivot problem. That loose end was tied up in 1973, when Manuel Blum, Robert Floyd, Vaughan Pratt, Ron Rivest, and Robert Tarjan — a remarkable roster, four of them future Turing Award winners — published the median-of-medians algorithm, the first selection method with a guaranteed O(n) worst case. It's a landmark result: you can find the median in linear time, worst case, which for a while people doubted was possible. The practical algorithm is still Hoare's quickselect (median-of-medians has a large constant); the theory chapter is BFPRT.

The intuition

Start exactly like quicksort: pick a pivot and partition, so everything smaller is left of the pivot and everything larger is right. Now the pivot is at its final sorted position — call it rank p, meaning it's the p-th smallest. Here's the whole insight: you wanted rank k. If p equals k, the pivot is your answer, and you're done. If k is less than p, the answer is somewhere in the left part, so recurse there — and completely ignore the right part, because nothing in it can be the k-th smallest. If k is greater, recurse right and ignore the left.

That one change from quicksort — recurse into one side instead of both — is what drops the cost from O(n log n) to O(n). Quicksort has to sort both halves because it needs the whole order; quickselect only needs one element, so it throws away half the array at every step and never looks back. You partition n elements, then about n/2, then n/4, and that sum is 2n — linear.

Complexity: how it scales

On average, with balanced-enough pivots, quickselect is $O(n)$: the partition sizes shrink geometrically, and $n + n/2 + n/4 + \cdots = 2n$. It's in place, $O(1)$ extra space. Like quicksort, it shares the pivot's curse — a consistently terrible pivot gives $O(n^2)$ — and the same fix applies: randomize the pivot to make that astronomically unlikely, or use median-of-medians to guarantee linear worst case. The chart finds the median of arrays of growing size, quickselect against sorting and against a heap:

What it's good at, what it isn't

Quickselect is the right tool whenever you need an order statistic and not the full order: the median of a dataset, a percentile for a latency report, the cutoff score for the top 100 applicants, the k-th nearest neighbor. In all of these, sorting computes an entire ordering you'll throw away to read one value; quickselect computes just enough to place that one value. It's in place and, on average, linear — asymptotically the best you can do, since you must at least look at every element once.

Its limits mirror quicksort's. The O(n²) worst case is real without a randomized or smart pivot. It rearranges the array (a side effect, if you needed the original order). And it finds a single rank efficiently — if you actually need many order statistics or the whole sorted sequence, just sort once. There's also a distribution subtlety the face-off exposes: a top-k heap (heapq.nsmallest) is O(n log k), which is excellent for small k (top ten of a million) but terrible for k near n/2 (the median), where log k is nearly log n. Quickselect is the tool that doesn't care where k falls.

The data, or the inputs

The face-off finds the median (the hardest rank, right in the middle) of random arrays at growing sizes, comparing quickselect to sorting and to a top-k heap. The animation runs quickselect on twelve elements seeking rank 6, recording each partition so you can watch it discard whole regions on its way to the answer.

Build it, one function at a time

The selection loop — partition, then narrow to the side that holds rank k, ignoring the other side entirely:

def quickselect(a, k, probe=None):
    """Return the k-th smallest element (0-indexed) in O(n) average time. Partition
    around a pivot; the pivot lands at some rank p. If p == k, the pivot is the
    answer. If k is smaller, recurse left; if larger, recurse right — and never
    touch the other side, which is where the speedup comes from."""
    a = list(a)
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        p = _partition(a, lo, hi, probe, k)
        if p == k:
            return a[p]
        if p < k:
            lo = p + 1          # the k-th smallest is to the right of the pivot
        else:
            hi = p - 1          # ... or to the left
    raise IndexError("k out of range")


def median(a):
    """The median via quickselect — O(n) average, no full sort. For an even count,
    average the two middle order statistics (two selects, still linear)."""
    n = len(a)
    if n % 2 == 1:
        return quickselect(a, n // 2)
    return (quickselect(a, n // 2 - 1) + quickselect(a, n // 2)) / 2

It reuses quicksort's partition unchanged — the same Lomuto sweep that drops the pivot into its final rank:

def _partition(a, lo, hi, probe=None, k=None):
    """Lomuto partition (same as quicksort): last element is the pivot; sweep,
    keeping a boundary i for the 'less than pivot' region; drop the pivot in at the
    end, where it reaches its final sorted rank."""
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if probe is not None:
            probe.append({"arr": list(a), "pivot": hi, "i": i, "j": j, "lo": lo, "hi": hi, "k": k, "placed": False})
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    if probe is not None:
        probe.append({"arr": list(a), "pivot": i, "i": i, "j": i, "lo": lo, "hi": hi, "k": k, "placed": True})
    return i

Watch it work

Here's quickselect on twelve bars, hunting for rank 6 — the pink bar marks the target position. Purple is the pivot, yellow the bar being compared, blue the "smaller than pivot" region, green a pivot that landed in its final rank, and dark bars are settled: regions quickselect has discarded because they're on the wrong side of the answer. Step through it and watch the dark settled region grow from both ends — every partition throws away a whole side that can't contain rank 6, so the search zeroes in fast, touching far fewer elements than a full sort would:

The complete code

Both versions in one place — flip between them. The from-scratch tab is quickselect reusing quicksort's partition. The library tab is the three built-in ways to select: sorted()[k] (O(n log n)), heapq.nsmallest (O(n log k)), and statistics.median — each right for a different shape of the problem.

"""Quickselect — find the k-th smallest element (the median, a percentile, the
top-k threshold) in O(n) average time WITHOUT sorting the whole array.

It's quicksort's partition put to a cleverer use. Quicksort recurses into BOTH sides
of the pivot; quickselect recurses into only the ONE side that contains the rank
you're after, because the other side can't hold the answer. Skipping that half turns
quicksort's O(n log n) into O(n): you do a partition over n, then n/2, then n/4, and
that geometric series sums to 2n.
"""


# region: quickselect
def quickselect(a, k, probe=None):
    """Return the k-th smallest element (0-indexed) in O(n) average time. Partition
    around a pivot; the pivot lands at some rank p. If p == k, the pivot is the
    answer. If k is smaller, recurse left; if larger, recurse right — and never
    touch the other side, which is where the speedup comes from."""
    a = list(a)
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        p = _partition(a, lo, hi, probe, k)
        if p == k:
            return a[p]
        if p < k:
            lo = p + 1          # the k-th smallest is to the right of the pivot
        else:
            hi = p - 1          # ... or to the left
    raise IndexError("k out of range")


def median(a):
    """The median via quickselect — O(n) average, no full sort. For an even count,
    average the two middle order statistics (two selects, still linear)."""
    n = len(a)
    if n % 2 == 1:
        return quickselect(a, n // 2)
    return (quickselect(a, n // 2 - 1) + quickselect(a, n // 2)) / 2
# endregion


# region: partition
def _partition(a, lo, hi, probe=None, k=None):
    """Lomuto partition (same as quicksort): last element is the pivot; sweep,
    keeping a boundary i for the 'less than pivot' region; drop the pivot in at the
    end, where it reaches its final sorted rank."""
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if probe is not None:
            probe.append({"arr": list(a), "pivot": hi, "i": i, "j": j, "lo": lo, "hi": hi, "k": k, "placed": False})
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    if probe is not None:
        probe.append({"arr": list(a), "pivot": i, "i": i, "j": i, "lo": lo, "hi": hi, "k": k, "placed": True})
    return i
# endregion

"""There's no `quickselect` in the standard library, but three built-ins do selection,
each with a different cost:

  - `sorted(a)[k]` — sort everything, then index. O(n log n): correct, simple, and the
    obvious thing — but it does far more work than needed for one element.
  - `heapq.nsmallest(k+1, a)[k]` — a heap-based partial sort. O(n log k), great when k
    is small (top-10 of a million), worse when k is near n/2 (the median).
  - `statistics.median(a)` — sorts internally, O(n log n).

So the face-off is quickselect's O(n) against sort-then-index's O(n log n): finding one
order statistic without paying to arrange all the others.
"""
import heapq
import statistics


# region: lib
def kth_smallest_sorted(a, k):
    """O(n log n): sort the whole array, then take index k."""
    return sorted(a)[k]


def kth_smallest_heapq(a, k):
    """O(n log k): a partial sort via a heap — cheap for small k, not for the median."""
    return heapq.nsmallest(k + 1, a)[k]


def median_lib(a):
    """statistics.median — sorts internally, O(n log n)."""
    return statistics.median(a)
# endregion

Scratch vs library

This face-off has the most interesting result in the tier. Finding the median of 400000 elements, our quickselect took about 43 ms and sorted()[k] about 49 ms — quickselect barely ahead, roughly a tie. That's remarkable when you remember quickselect is O(n) and sorting is O(n log n): the algorithm with the better complexity is only breaking even, because it's interpreted Python racing a C-optimized sort. The O(n) advantage is real — it's exactly what lets our Python code keep up with C at all — and in a compiled language quickselect would win clearly. The heapq.nsmallest line tells the other half: at 274 ms it's six times slower than either, because finding the median with a top-k heap means k = n/2, and O(n log k) with a huge k is just a slow sort. The lesson is the tier's recurring one — Big-O sets the ceiling, the constant and the specific k decide the race — and the practical takeaway is to pick the selection tool that matches where k falls.

Where you'll actually meet it

Quickselect runs wherever a percentile or threshold is needed without a full sort. It's numpy.partition and std::nth_element, the functions data and scientific libraries provide precisely for this. Monitoring systems compute p50/p95/p99 latencies with it. Machine learning uses it for k-nearest-neighbors (find the k closest without sorting all distances) and for feature selection by percentile. Databases use it for approximate median and quantile queries. Any time you catch yourself sorting an array just to grab one element out of the middle, quickselect is the tool that does only the work the question requires.

Takeaways

Quickselect finds the k-th smallest element in $O(n)$ average time by partitioning like quicksort and recursing into only the side that contains rank k — the single change from quicksort that turns O(n log n) into O(n). It's the tool for medians, percentiles, and top-k thresholds: one order statistic without arranging the rest. It shares quicksort's pivot risk (randomize it) and, in the median-of-medians variant, achieves guaranteed linear time — a theoretical landmark.

That closes the recursion-and-sorting tier, and with it this stretch of the book: from recursion and the six sorts through searching and selection, you now have the toolkit for arranging and finding in linear structures. The next tier changes the shape of the data entirely. Trees give up the array's flat layout for a branching one, and in exchange they make insertion, deletion, and ordered search all $O(\log n)$ at once — the balanced combination no structure so far has managed. The binary search tree is where it begins.