Selection & Order Statistics: Quickselect, Median of Medians, and Top-K

1. Problem and Motivation

Many interview and systems problems ask for one statistic of an unsorted collection: the median salary, the 90th-percentile latency, the k-th cheapest flight, or the top-10 trending posts. The naive answer is always the same — sort everything, then index into the result. Sorting is correct, but it does far more work than the question requires: it fully orders every element when the question only needs one position, or a small prefix, of that order.

Selection is the problem of finding the k-th smallest (or largest) element of a collection without fully sorting it. Order statistics is the broader name for the family of quantities — minimum, maximum, median, k-th smallest, percentiles — that selection algorithms compute. This lesson builds the toolbox interviewers expect: quickselect for expected-linear selection, median of medians for a deterministic worst-case guarantee, heap-based top-k for streaming data, and the two-heap trick for maintaining a running median.

2. Prerequisites

• Array partitioning: quickselect reuses the exact Lomuto/Hoare partition step from quicksort. If the partition invariant — everything left of the pivot is no greater than it, everything right is no smaller — is not fresh, review the Partition Trace in the Fundamental Sorting guide before continuing; this lesson does not re-derive it.
• Heap push/pop mechanics: the heap-based sections assume you can already insert into and extract from a binary heap in $O(\log n)$. See the Heap Operations section of the Heaps, Sorting & Hashing guide for that mechanics; it is not repeated here.
• Recursion and recurrences: comfort with recursive divide-and-conquer calls and reading a recurrence like $T(n) = T(n/2) + O(n)$ is assumed.
• Randomized algorithms: know the difference between a worst-case bound (true for every input) and an expected bound (an average over random choices, for a fixed input).

3. A Concrete Example

4. Core Insight

1. Pick a pivot from the active range and partition so smaller values land left, larger values land right.
2. Note the pivot's final index after partitioning.
3. If the pivot index equals the target index, the pivot is the answer — stop.
4. If the pivot index is greater than the target, the answer is to the left — recurse (or loop) into the left range only.
5. If the pivot index is less than the target, the answer is to the right — recurse (or loop) into the right range only, adjusting nothing about the target index itself since it is an absolute array position.

5. Correctness and Why It Works

Correctness follows directly from the partition invariant, by induction on the size of the active range:

1. Invariant: after partitioning range [lo, hi] around a pivot that lands at index p, every element in [lo, p-1] is $\le$ the pivot and every element in [p+1, hi] is $\ge$ the pivot.
2. Base case: a range of one element trivially has that element as its own k-th smallest.
3. Inductive step: if the target index equals p, the pivot is provably the target-th smallest element of the whole original array, because exactly p - lo elements in this range (and, by the outer recursion, none outside it) are smaller. If the target is less than p, it must lie among the p - lo elements known to be $\le$ the pivot, so recursing left preserves correctness on a strictly smaller range. The symmetric argument holds for recursing right.
4. Termination: the active range shrinks by at least one element every partition (the pivot itself is excluded from the next range), so the recursion terminates.

That argument says nothing about speed — it holds no matter how badly the pivot is chosen. The speed argument is separate and probabilistic. If a pivot is "good" (it lands roughly in the middle of the active range, say between the 25th and 75th percentile), the range at least halves. Assume for intuition that pivots are always good: then the range sizes form the sequence $n, n/2, n/4, \dots$, and the work done per level is proportional to the range size, giving the recurrence

$$T(n) = T(n/2) + O(n)$$

whose solution is $T(n) = O(n)$, because the geometric series $n + n/2 + n/4 + \cdots$ sums to $O(n)$ rather than the $O(n \log n)$ you get when both halves must be visited, as in sorting. A pivot lands in the "good" middle 50% of any range with probability $1/2$ regardless of the input's arrangement, so on average only two partition attempts are needed per level to get a good split, which keeps the expected total work at $O(n)$. Section 8 makes this expectation argument precise for randomized quickselect and explains why it can fail without randomization.

6. Complexity Analysis

Every one of these beats the $\Theta(n \log n)$ lower bound that applies to sorting, and that is not a contradiction: the comparison-sort lower bound applies to producing a total order over all $n$ elements, but selection only needs to identify one position (or a bounded set of positions) in that order, which is a strictly easier question with a lower information requirement.

7. Three-Language Implementation

Each panel implements randomized quickselect with an in-place Lomuto partition and returns the k-th smallest element (1-indexed) of the sample array from Section 3.

import random

def quickselect(values, k):
    """Return the k-th smallest element (1-indexed) of values."""
    if not values:
        raise ValueError("quickselect is undefined for an empty sequence")
    if not (1 <= k <= len(values)):
        raise ValueError("k is out of range")

    def partition(items, lo, hi):
        pivot_index = random.randint(lo, hi)
        items[pivot_index], items[hi] = items[hi], items[pivot_index]
        pivot = items[hi]
        store = lo
        for i in range(lo, hi):
            if items[i] <= pivot:
                items[i], items[store] = items[store], items[i]
                store += 1
        items[store], items[hi] = items[hi], items[store]
        return store

    items = list(values)
    lo, hi, target = 0, len(items) - 1, k - 1
    while lo < hi:
        pivot_index = partition(items, lo, hi)
        if pivot_index == target:
            return items[pivot_index]
        elif pivot_index < target:
            lo = pivot_index + 1
        else:
            hi = pivot_index - 1
    return items[lo]

sample = [7, 10, 4, 3, 20, 15]
print("3rd smallest:", quickselect(sample, 3))  # 3rd smallest: 7

#include <iostream>
#include <random>
#include <stdexcept>
#include <vector>

int partition(std::vector<int>& items, int lo, int hi) {
    static std::mt19937 rng{std::random_device{}()};
    std::uniform_int_distribution<int> dist(lo, hi);
    int pivotIndex = dist(rng);
    std::swap(items[pivotIndex], items[hi]);
    int pivot = items[hi];
    int store = lo;
    for (int i = lo; i < hi; ++i) {
        if (items[i] <= pivot) {
            std::swap(items[i], items[store]);
            ++store;
        }
    }
    std::swap(items[store], items[hi]);
    return store;
}

int quickselect(std::vector<int> items, int k) {
    if (items.empty()) {
        throw std::invalid_argument("quickselect is undefined for an empty sequence");
    }
    if (k < 1 || k > static_cast<int>(items.size())) {
        throw std::invalid_argument("k is out of range");
    }
    int lo = 0, hi = static_cast<int>(items.size()) - 1, target = k - 1;
    while (lo < hi) {
        int pivotIndex = partition(items, lo, hi);
        if (pivotIndex == target) {
            return items[pivotIndex];
        } else if (pivotIndex < target) {
            lo = pivotIndex + 1;
        } else {
            hi = pivotIndex - 1;
        }
    }
    return items[lo];
}

int main() {
    std::vector<int> sample{7, 10, 4, 3, 20, 15};
    std::cout << "3rd smallest: " << quickselect(sample, 3) << '\n'; // 3rd smallest: 7
}

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Quickselect {
    private static final Random RNG = new Random();

    private static void swap(List<Integer> items, int i, int j) {
        int temp = items.get(i);
        items.set(i, items.get(j));
        items.set(j, temp);
    }

    private static int partition(List<Integer> items, int lo, int hi) {
        int pivotIndex = lo + RNG.nextInt(hi - lo + 1);
        swap(items, pivotIndex, hi);
        int pivot = items.get(hi);
        int store = lo;
        for (int i = lo; i < hi; i++) {
            if (items.get(i) <= pivot) {
                swap(items, i, store);
                store++;
            }
        }
        swap(items, store, hi);
        return store;
    }

    static int quickselect(List<Integer> values, int k) {
        if (values.isEmpty()) {
            throw new IllegalArgumentException("quickselect is undefined for an empty sequence");
        }
        if (k < 1 || k > values.size()) {
            throw new IllegalArgumentException("k is out of range");
        }
        List<Integer> items = new ArrayList<>(values);
        int lo = 0, hi = items.size() - 1, target = k - 1;
        while (lo < hi) {
            int pivotIndex = partition(items, lo, hi);
            if (pivotIndex == target) {
                return items.get(pivotIndex);
            } else if (pivotIndex < target) {
                lo = pivotIndex + 1;
            } else {
                hi = pivotIndex - 1;
            }
        }
        return items.get(lo);
    }

    public static void main(String[] args) {
        List<Integer> sample = List.of(7, 10, 4, 3, 20, 15);
        System.out.println("3rd smallest: " + quickselect(sample, 3)); // 3rd smallest: 7
    }
}

8. Selection Algorithms Deep Dive

Quickselect

Quickselect is quicksort's partition step reused for a single recursive branch instead of two. Using a Lomuto partition (scan once, move elements $\le$ the pivot to the front) or a Hoare partition (two inward-moving pointers) makes no difference to the asymptotic argument, only to the constant factor and the number of swaps. With a "good" pivot every time, the recurrence $T(n) = T(n/2) + O(n)$ gives $O(n)$ average time, as derived in Section 5.

The trouble is picking the pivot deterministically without randomness. A common naive choice is "always the first element" or "always the last element." On an already-sorted (or reverse-sorted, or adversarially constructed) array, that choice makes the partition split off exactly one element every time: the range shrinks from $n$ to $n-1$ to $n-2$, giving the recurrence $T(n) = T(n-1) + O(n)$, whose solution is $T(n) = O(n^2)$. This is not a rare edge case — it is the worst case for the exact class of input (sorted or nearly sorted data) that shows up constantly in real systems, which is precisely why a fixed pivot rule is dangerous in production code.

Randomized Quickselect

Choosing the pivot uniformly at random from the active range, independently on every call, breaks the adversary's ability to construct a bad input in advance — the algorithm's performance no longer depends on the input's arrangement at all, only on its own coin flips. A pivot chosen uniformly from a range of size $m$ lands strictly between the 25th and 75th percentile with probability $1/2$; whenever that happens, the range shrinks to at most $3m/4$. Summing a geometric series of expected work over levels where the range shrinks by a constant factor with constant probability per attempt gives expected total work $O(n)$, and this expectation holds for every input — there is no adversarial array, because the adversary cannot predict the random draws. This makes randomized quickselect a Las Vegas algorithm: it is always correct, and only its running time is a random variable, with worst case $O(n^2)$ occurring with vanishingly small probability (roughly $2^{-n}$ for consistently bad draws).

Median of Medians (BFPRT)

Randomization removes the adversarial-input problem in expectation, but some settings — real-time systems, security-sensitive code, or anywhere a guaranteed bound is contractually required — need a worst-case $O(n)$ guarantee with no randomness at all. The median of medians algorithm (Blum, Floyd, Pratt, Rivest, Tarjan — BFPRT) achieves this by choosing the pivot more carefully instead of faster:

selectDeterministic(A, k):
    if length(A) <= 5:
        sort A directly and return the k-th element

    split A into groups of 5 elements each (last group may be smaller)
    find the median of each group by direct sorting (constant work per group)
    medianOfMedians = selectDeterministic(list of group medians, middle index)

    partition A around medianOfMedians as the pivot
    recurse into whichever side contains index k, exactly as in quickselect

The intuition: sorting each 5-element group and taking its median is $O(1)$ work repeated $n/5$ times, so finding all group medians costs $O(n)$. The median of those $n/5$ medians is, informally, "typical" of the whole array — at least half of the group medians are $\le$ it, and each of those groups contributes at least 3 of its 5 elements (the median and the two below it) that are also $\le$ it, so the pivot is guaranteed to be $\ge$ roughly 30% and $\le$ roughly 70% of all elements. That guarantee, unlike a random pivot's probable good split, holds for every input, every time. The two recursive calls — one over $n/5$ medians, one over at most $7n/10$ remaining elements — combine into $T(n) = T(n/5) + T(7n/10) + O(n)$, and because $1/5 + 7/10 \lt 1$, the recursive work shrinks fast enough that the total stays $O(n)$. The full proof of that recurrence is more delicate than the quickselect case and is usually left to a dedicated algorithms course; the takeaway for interview purposes is the mechanism (group into 5s, recurse on medians, use that as a guaranteed-balanced pivot) rather than the recurrence algebra.

In practice, median of medians has a larger constant factor than randomized quickselect because of the grouping and repeated sorting overhead, so libraries like C++'s std::nth_element use an introselect strategy: run quickselect with a reasonable pivot rule, but fall back to median of medians (or a heap-based method) if recursion depth suggests the input is adversarial. This mirrors introsort's quicksort-with-heapsort-fallback design.

k-th Largest via Heap

Quickselect assumes the entire array is available up front. When data arrives one item at a time — a stream of sensor readings, log lines, or scores — and only a small, fixed $k$ matters, a heap is the better tool. Maintain a min-heap of size at most $k$: push each new value, and whenever the heap grows past $k$ elements, pop the minimum. After processing the whole stream, the heap's minimum is the k-th largest value seen, and the heap's contents are the top-$k$ set. Each push/pop is $O(\log k)$ (see the Heap Operations section for that mechanics — it is not rederived here), so the total cost over $n$ arrivals is $O(n \log k)$.

Compare the two approaches by what they assume: quickselect needs random access to the full collection and gives one answer once, in expected $O(n)$; the heap approach processes data incrementally, uses only $O(k)$ memory regardless of how large the stream grows, and can report the current answer at any moment. When $k$ is small and fixed and the data is a stream or too large to hold in memory, $O(n \log k)$ with $O(k)$ space wins even though it is asymptotically slower than expected-$O(n)$ quickselect for a static array.

Streaming Median with Two Heaps

The median is the order statistic at the very middle of the data, and maintaining it under a continuous stream of insertions is a common capstone interview problem (LeetCode 295, "Find Median from Data Stream"). The trick is to split the data into two balanced halves, each kept in its own heap:

• A max-heap holding the smaller (lower) half of the values seen so far, so its top is the largest of the small values.
• A min-heap holding the larger (upper) half of the values seen so far, so its top is the smallest of the large values.

insert(x):
    if lowerHalf is empty or x <= lowerHalf.top():
        push x onto lowerHalf (max-heap)
    else:
        push x onto upperHalf (min-heap)

    // rebalance so the heaps differ in size by at most 1
    if size(lowerHalf) > size(upperHalf) + 1:
        move lowerHalf.top() to upperHalf
    else if size(upperHalf) > size(lowerHalf) + 1:
        move upperHalf.top() to lowerHalf

median():
    if size(lowerHalf) == size(upperHalf):
        return (lowerHalf.top() + upperHalf.top()) / 2
    return the top of whichever heap is larger

Every insertion pushes onto one heap and possibly moves one element between heaps, so it costs $O(\log n)$; every median query just peeks at one or two heap tops, so it costs $O(1)$. This is a direct capstone application of the heap mechanics from the prerequisites: the only new idea is keeping two heaps balanced against each other instead of one heap against a fixed size $k$.

9. Applications and Alternatives

Alternatives worth naming in an interview: a full sort ($O(n \log n)$) is still the right choice when you need several different order statistics from the same data, or the data will be queried repeatedly and re-sorting per query would be wasteful. Counting sort or radix-based selection can reach $O(n)$ deterministically without any partitioning when the value range is small and known in advance, trading generality for speed. Introselect (median-of-medians as a worst-case fallback for quickselect) is the production-grade default because it keeps the fast average case while eliminating the quadratic worst case entirely.

10. Exercises and Mastery

Easy

1. Write out the total comparison work for finding the median of an $n$-element array by (a) sorting the whole array and reading the middle, versus (b) quickselect. State both complexities and explain, in one sentence, when approach (a) is still the more sensible engineering choice despite being asymptotically slower for a single query.
2. Trace randomized quickselect by hand on [9, 1, 8, 2, 7] to find the 2nd smallest, choosing the middle element of each active range as the pivot instead of the last.

Medium

1. Kth Largest Element in a Stream (LeetCode 703): design a class that, given an integer $k$, supports adding a new value to a running stream and always reports the current k-th largest value. Maintain a min-heap of size at most $k$ as described in Section 8; adding a value is $O(\log k)$, and the answer is always the heap's minimum.
2. Extend the two-heap median tracker to also support removing an arbitrary previously-inserted value (a "lazy deletion" variant using deferred cleanup), and explain what invariant is harder to maintain once removal is allowed.

Hard

1. Median of Two Sorted Arrays (LeetCode 4): given two already-sorted arrays of size $m$ and $n$, find the combined median. A correct and well-explained $O(m+n)$ approach merges the two arrays with a two-pointer walk (as in merge sort's merge step) just far enough to reach the middle position(s), without allocating the full merged array. State clearly that this problem is really "select the k-th element of the union of two sorted sequences," which connects it to selection-by-predicate: you can binary-search directly on a candidate answer value or on a split point between the two arrays to reach $O(\log(\min(m,n)))$ — a genuinely faster solution exists, but deriving it rigorously is beyond what this exercise requires; the $O(m+n)$ merge-based solution is sufficient here.

Review rhythm: tomorrow, redo the quickselect hand trace from memory and state why randomization matters without looking at Section 8. Next week, implement median of medians well enough to explain the 30/70 split argument out loud. Several weeks later, solve a new streaming problem (rate limiting, sliding-window percentile) by recognizing it as a selection or two-heap problem in disguise, then teach the quickselect-versus-heap tradeoff to someone who has not seen either.

11. Summary Cheat Sheet

• Selection finds the k-th order statistic without fully sorting; it beats the $\Omega(n \log n)$ sorting lower bound because it answers a strictly narrower question.
• Quickselect recurses into only the side of a partition that can contain the target index, giving the recurrence $T(n) = T(n/2) + O(n) = O(n)$ when pivots are good.
• A fixed pivot rule (first/last element) is $O(n^2)$ worst case on sorted or adversarial input; a uniformly random pivot makes that worst case independent of the input (Las Vegas, expected $O(n)$).
• Median of medians (BFPRT) groups elements into 5s to pick a pivot that is provably between the 30th and 70th percentile every time, giving deterministic worst-case $O(n)$ with no randomness.
• A size-$k$ min-heap gives the k-th largest of a stream in $O(n \log k)$ time and $O(k)$ space — the right tool when data arrives incrementally and $k$ is small and fixed.
• Two balanced heaps (max-heap for the lower half, min-heap for the upper half) maintain a running median in $O(\log n)$ per insertion and $O(1)$ per query.
• Median of Two Sorted Arrays reframes as selecting the k-th element of a union; an $O(m+n)$ merge-based walk is sufficient, though an $O(\log(\min(m,n)))$ binary-search solution exists.