Quickselect and the Cost of Finding One Element in Place

Sorting produces every order statistic at once and costs $n \log n$. Finding the median, or the tenth largest, or the element that would sit at index $k$, needs one of them, and the same partition step that drives quicksort can find it in linear expected time. The difference is what happens after the partition: quicksort recurses on both sides, selection recurses on one.

One-sided recursion

Partition the array around a pivot. The pivot lands at some index $p$, everything before it is smaller and everything after is larger. If $p = k$, the answer is at $p$. If $k < p$, the answer is in the left part and the right part can be discarded entirely. If $k > p$, the reverse.

/* returns the k-th smallest element (0-based) of a[lo..hi]; reorders a */
static int select_kth(int *a, size_t lo, size_t hi, size_t k)
{
    while (lo < hi) {
        size_t p = hoare_partition(a, lo, hi);   /* lo <= p < hi */
        if (k <= p)      hi = p;
        else             lo = p + 1;
    }
    return a[lo];
}

The loop is the tail-recursive form: only the side containing the target is followed, so the other side is abandoned rather than sorted. That single change is the entire asymptotic difference. Quicksort’s recurrence is $T(n) = 2T(n/2) + \Theta(n)$, giving $n \log n$. Selection’s is $T(n) = T(n/2) + \Theta(n)$ for a balanced split, giving the geometric series $n + n/2 + n/4 + \cdots = 2n$. Reaching a single element needs a working partition to agree with the bound it reports, so this form assumes the Hoare partition from quicksort partition schemes, which returns lo <= p < hi and never places an element equal to the pivot on the wrong side.

Why the expected cost is linear, not just the balanced case

A random pivot does not give balanced splits, but the sum of the subproblem sizes is still linear in expectation. If every pivot rank were equally likely, the target side would have expected size $3n/4$, and the expected total work would follow the geometric series $n + \tfrac{3}{4}n + (\tfrac{3}{4})^2 n + \cdots$, converging to $4n$. Sampling is without replacement, so the successive subproblems are not independent, and the expected size of the next subproblem after a split of size $n$ is not exactly three quarters of $n$; the geometric argument is a bound on the shape of the sum rather than a computation of it.

The exact expectation for random pivots follows from summing, over every ordered pair of keys, the probability that the pair is compared at some point. For randomised quicksort that sum is $2(n+1)H_n - 4n$ comparisons, where $H_n$ is the $n$-th harmonic number, giving a leading constant of $2\ln 2 \approx 1.39$ times $n$. Selection compares fewer pairs, since it discards the side away from the target and never partitions it, so its median is also linear with a smaller constant. Whatever the constant, the structure is the same: the shrink factor is bounded away from 1 by a constant in expectation, so the series is geometric and the total is $O(n)$. The minimum or maximum is cheaper still, at $n-1$ comparisons, because the first partition settles it.

Contrast this with quicksort, where both sides are processed and the sum over a level is always $n$, giving $n$ per level and $\log n$ levels. Selection’s cost is dominated by the first partition and decays from there; in the common case it does one full pass and a fraction of a second.

The worst case is the same quadratic

Nothing above rules out a pivot that lands at the extreme end every time. With the first or last element as pivot, an already-sorted array yields a 0-to-$n-1$ split at every level, and the subproblem sizes are $n, n-1, n-2, \ldots$, summing to $\Theta(n^2)$. Selection inherits quicksort’s adversarial weakness exactly.

Median-of-three removes the sorted and reverse-sorted cases and costs at most three comparisons per level. It does not remove the weakness: an input can be constructed to make median-of-three choose badly, and the construction is not obscure. Randomised pivot selection makes the expected bound hold for every fixed input, because the adversary cannot know the random choices; the worst case remains quadratic but only with negligible probability over the algorithm’s own randomness.

The answer that does not depend on the input, as in quicksort, is a depth budget. Track the number of partitions performed and switch to a guaranteed-linear method when the count exceeds a threshold proportional to $\log n$. The guaranteed method is median-of-medians, whose constant is large enough that it is only worth invoking as a fallback. Combining a fast randomised path with that fallback is the introselect strategy, and the C++ standard specifies nth_element as linear on average rather than in the worst case, which is the guarantee such a combination provides.

Duplicates break it in the same way

An array of identical keys partitioned with a two-way scheme produces an empty side and a side of size $n-1$ at every step, so selection becomes quadratic even though the answer is trivially the first element. The failure is identical to the one described in quicksort partition schemes, and the fix is identical: a three-way partition that returns the boundaries of the equal region.

With three-way partitioning, if $k$ falls inside the equal region the answer is the pivot value and the search ends immediately. A large group of duplicates is resolved in one pass, which is the behaviour a caller sorting records by a coarse key needs.

Floyd–Rivest and sampling the pivot

The constant in the expected cost can be reduced by choosing a better pivot cheaply. Floyd and Rivest’s method samples a small number of elements, sorts the sample, and uses two sampled order statistics to bracket the target, then partitions only the bracketed range. With a sample size that grows with $n$ but stays sublinear, the expected comparison count falls to $n + o(n)$: a leading constant of 1 plus lower-order terms, against a constant materially above 1 for the plain randomised algorithm.

The reason this works is that the sample gives a high-probability bound on where the target lies, so the first partition operates on a range much smaller than $n$. The sample itself is small enough that sorting it costs little. The trade is that the method’s analysis and implementation are more delicate: the sample size must be chosen as a function of $n$, the bracketing must handle the case where the target falls outside the bracket, and the fallback path is a full quickselect.

The same idea appears in practical implementations as a sampling pivot rule: examine a fixed number of evenly spaced elements, take their median, and partition. It is simpler than Floyd–Rivest and captures much of the benefit, because a median of a sample concentrates near the true median.

Selection versus partial sorting

When the requirement is not one element but the $k$ smallest in order, the choices are different. Sorting everything costs $n \log n$. Selecting the $k$-th element and then sorting the $k$ elements below it costs $\Theta(n) + k \log k$, which is the right answer for small $k$. Maintaining a max-heap of size $k$ costs $n \log k$ and streams the input, so it needs no random access and works on data that arrives over time.

The heap approach deserves the comparison because it dominates when $k$ is small and the input is a stream. For $k = 10$ and $n = 10^9$, the heap holds ten elements and each new element is compared against the heap’s root; the vast majority fail the comparison and cost nothing beyond one read. The selection approach requires the whole array in memory and touches every element.

At the other extreme, when $k$ is a constant fraction of $n$, the heap costs $n \log k$, which is within a constant factor of $n \log n$, so the simpler full sort is competitive and the heap’s streaming property stops mattering. The heap’s real advantage is confined to small $k$, where relative to selection it avoids holding the whole input and touches each arriving element once instead of requiring random access to an array.

What selection guarantees and what it does not

Selection guarantees the element at the requested rank, and it guarantees the partition property: every element before the answer is $\le$ it and every element after is $\ge$ it. That is enough for many callers, including those that need a median filter, a percentile, or a split into “small” and “large” groups.

It does not sort the sides. Two elements on the same side of the answer have no defined relative order, and successive selections on the same array can leave it in different states depending on the pivot choices. Code that calls selection and then assumes the prefix is sorted is relying on an accident of one implementation.

Selection also mutates the input. The reordering is a side effect, and the standard library permits it: nth_element guarantees the partition property and says nothing about the order of the two sides, so it is allowed to permute them freely. Callers who need the original order must copy first, which costs $\Theta(n)$ and removes much of the advantage over sorting a copy.