Order Statistics: Randomized Quickselect vs Deterministic BFPRT Median-of-Medians

Hoare's Quickselect (FIND, 1961): Expected $\Theta(N)$ Selection

Given an unsorted array $A[0 \dots n-1]$ and a target rank $k \in [0, n-1]$, the selection problem asks to rearrange $A$ (like C++'s std::nth_element) such that $A[k]$ holds the element that would appear at index $k$ if $A$ were sorted, with $A[0 \dots k-1] \le A[k] \le A[k+1 \dots n-1]$.

Randomized Quickselect picks a random pivot, partitions $A[lo \dots hi]$ around it to land at index $p$, and branches three ways:

• If $k == p$: Done! Return $A[p]$.
• If $k < p$: Recurse (or loop) only on the left subarray $A[lo \dots p-1]$.
• If $k > p$: Recurse (or loop) only on the right subarray $A[p+1 \dots hi]$.

Because a random pivot lands in the middle $50\%$ of the current subarray (ranks $[n/4, 3n/4]$) with probability $1/2$, every $2$ expected partitions shrink the active subarray to at most $\frac{3}{4}$ of its previous size. Summing the geometric series gives:

More precisely, using indicator random variables $X_{ij}$, Quickselect performs at most $2(n + 1 + (k+1)\ln\frac{n}{k} + (n-k)\ln\frac{n}{n-k}) \le (2 + 2\ln 2)n \approx 3.386n$ expected comparisons to find the median, and $2n + o(n)$ to find the minimum or maximum.

Why Groups of $5$? Why Do Groups of $3$ Fail While Groups of $7$ Work?

Production C++20 Implementation: Iterative 3-Way Quickselect & In-Place BFPRT

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <utility>

template <std::totally_ordered T>
void small_insertion_sort(T* a, std::size_t lo, std::size_t hi) noexcept {
    for (std::size_t i = lo + 1; i <= hi; ++i) {
        T v = std::move(a[i]);
        std::size_t j = i;
        while (j > lo && v < a[j - 1]) {
            a[j] = std::move(a[j - 1]);
            --j;
        }
        a[j] = std::move(v);
    }
}

// Deterministic In-Place BFPRT (Median-of-Medians) with 3-Way Partitioning for Duplicates
template <std::totally_ordered T>
void bfprt_select(T* a, std::size_t lo, std::size_t hi, std::size_t k) noexcept {
    while (hi - lo > 16) {
        const std::size_t n = hi - lo + 1;
        const std::size_t num_groups = n / 5;

        // 1. Sort each group of 5 in-place and swap its median to the front [lo .. lo + num_groups - 1]
        for (std::size_t g = 0; g < num_groups; ++g) {
            const std::size_t g_lo = lo + g * 5;
            small_insertion_sort(a, g_lo, g_lo + 4);
            std::swap(a[lo + g], a[g_lo + 2]);
        }

        // 2. Recursively select the exact median of the group medians at a[lo + num_groups / 2]
        const std::size_t mom_idx = lo + num_groups / 2;
        bfprt_select(a, lo, lo + num_groups - 1, mom_idx);
        const T pivot = a[mom_idx];

        // 3. 3-Way Dutch National Flag Partition around pivot (handles all-equal keys in O(N)!)
        std::size_t lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (a[i] < pivot)      std::swap(a[lt++], a[i++]);
            else if (pivot < a[i]) std::swap(a[i], a[gt--]);
            else                   ++i;
        }

        // 4. Tail-loop into whichever region contains target rank k
        if (k < lt) {
            hi = lt - 1;
        } else if (k > gt) {
            lo = gt + 1;
        } else {
            return; // k lies inside [lt .. gt], so a[k] == pivot is in its exact final spot!
        }
    }
    small_insertion_sort(a, lo, hi);
}