Quicksort (Divide and Conquer by Partitioning) — Senior Level¶

Quicksort is rarely "just an algorithm" in production — it is the engine inside qsort, Arrays.sort, sort.Slice, and std::sort, where a single bad pivot policy can turn a O(n log n) workhorse into an O(n²) denial-of-service vector. At senior level the questions are: how do real standard libraries make quicksort robust (introsort, pattern-defeating quicksort), how do adversaries attack it, and how do you build, observe, and test a sort you can trust under hostile load.

Table of Contents¶

1. Introduction
2. Introsort: Quicksort with a Heapsort Fallback
3. Adversarial Inputs and Algorithmic-Complexity Attacks
4. Hybrid Sorts in Standard Libraries
5. Engineering the Partition
6. Quickselect in Production
7. Code Examples
8. Observability and Testing
9. Failure Modes
10. Summary

1. Introduction¶

At the senior level the question is no longer "how does partitioning work" but "what breaks when this sort runs on untrusted data at scale, and how do the standard libraries defend against it?". Quicksort shows up in three production guises that share one engine:

1. The default comparison sort — std::sort, Arrays.sort(int[]), Go's sort.Slice, C's qsort are all quicksort-derived. They must never blow up to O(n²) on real or adversarial input.
2. Selection — std::nth_element, "top-k", percentile/median computation are quickselect, expected O(n), and must resist the same attacks.
3. The hybrid core — every serious implementation is a hybrid: quicksort for the bulk, insertion sort for small ranges, and heapsort (or a different pivot policy) as a worst-case guard.

The senior decisions are: how to guarantee O(n log n) despite quicksort's O(n²) worst case (introsort), how to neutralize adversaries who craft killer inputs (randomization, pattern-defeating pivots), how to make the partition fast (branch prediction, block partitioning), and how to verify correctness and detect pathological behavior in production.

2. Introsort: Quicksort with a Heapsort Fallback¶

Introsort (David Musser, 1997) is the standard answer to quicksort's O(n²) worst case. The idea: run quicksort, but monitor the recursion depth. If it exceeds a threshold of 2⌊log₂ n⌋ — a strong signal that pivots are going badly — switch that subarray to heapsort, which guarantees O(n log n). Below a small size, switch to insertion sort.

introsort(a):
    depthLimit = 2 * floor(log2(len(a)))
    introsort_rec(a, 0, len(a)-1, depthLimit)

introsort_rec(a, lo, hi, depthLimit):
    while hi - lo > THRESHOLD:          # ~16
        if depthLimit == 0:
            heapsort(a, lo, hi)          # WORST-CASE GUARD: guaranteed O(n log n)
            return
        depthLimit--
        p = partition(a, lo, hi)         # median-of-three pivot
        introsort_rec(a, p+1, hi, depthLimit)  # recurse one side
        hi = p                                  # loop the other (tail-call elim)
    insertion_sort(a, lo, hi)            # finish small ranges cheaply

Why this works:

• Common case: good pivots, depth stays O(log n), you get quicksort's speed and small constant.
• Adversarial / unlucky case: depth hits the limit, heapsort takes over for that subtree only, guaranteeing the whole sort is O(n log n).
• Small ranges: insertion sort avoids recursion overhead and is fast on nearly-sorted data.

Introsort is what std::sort is required to be (the C++ standard mandates O(n log n) worst case since C++11, which rules out plain quicksort). It is the canonical example of combining three sorts so each covers the others' weaknesses: quicksort's speed, heapsort's worst-case guarantee, insertion sort's small-range efficiency.

The depth limit 2⌊log₂ n⌋ is chosen because a perfectly balanced quicksort has depth ⌊log₂ n⌋; allowing twice that tolerates moderate imbalance (constant-fraction splits) while catching the runaway O(n)-depth case quickly, before quadratic time accrues.

3. Adversarial Inputs and Algorithmic-Complexity Attacks¶

Quicksort's O(n²) worst case is a security concern, not just a performance footnote. If an attacker can feed input to a sort whose pivot rule is deterministic and known, they can construct a "killer" input that forces O(n²), causing a CPU-exhaustion denial of service.

3.1 The median-of-three killer¶

Even median-of-three is not safe against a determined adversary. M. Douglas McIlroy's 1999 paper "A Killer Adversary for Quicksort" shows how to construct, on the fly, an input that forces any deterministic quicksort (including median-of-three) into O(n²). The trick: an adversarial comparator that decides element order lazily to always make the chosen pivot extreme. This famously caused real qsort implementations to run quadratically.

3.2 Defenses¶

The strongest practical posture combines randomization (makes targeted attacks infeasible) with the introsort depth guard (bounds the damage even in the worst case). Randomization alone leaves an astronomically unlikely worst case; the depth guard removes it entirely. This is why hash-table and sort DoS (the "algorithmic complexity attack" family, Crosby-Wallach 2003) is mitigated by both unpredictable randomness and a guaranteed-O(n log n) fallback.

3.3 Hostile comparators¶

A subtler failure: a user-supplied comparator that is inconsistent (violates the strict-weak-ordering contract — e.g., cmp(a,b) and cmp(b,a) both return "less"). This can drive pointers past array bounds in an optimized Hoare partition that relies on the pivot acting as a sentinel. Java's Arrays.sort famously throws IllegalArgumentException: Comparison method violates its general contract! precisely to surface this. Senior implementations either validate the comparator or write partition loops that are memory-safe even under a broken comparator.

4. Hybrid Sorts in Standard Libraries¶

No production sort is "pure" quicksort. The dominant designs:

Two ideas worth a senior's attention:

Dual-pivot quicksort (Yaroslavskiy). Java's primitive sort partitions around two pivots p1 ≤ p2 into three regions: < p1, p1 ≤ x ≤ p2, > p2. It does fewer cache misses and comparisons on many real inputs, which is why JDK 7+ adopted it for primitive arrays. It is not stable (fine for primitives, where equal elements are indistinguishable).

Pattern-defeating quicksort (pdqsort, Orson Peters 2014). Used by Rust and Go. It combines: median-of-three / ninther pivots; an introsort-style depth guard; a check that detects when a partition is highly unbalanced and reacts by shuffling a few elements to break adversarial or already-partially-sorted patterns; and an optimization that detects already-sorted runs to achieve near-O(n) on sorted input. It also uses block partitioning (Section 5) for branchless speed. pdqsort is the current state of the art for unstable in-place sorting.

4.1 Anatomy of a production hybrid (decision flow)¶

A real-world unstable sort makes a cascade of decisions per subarray. Reading them as a flow clarifies why each piece exists:

sort(range):
  if size <= 16:                      -> insertion sort     # small-range efficiency
  if recursion_depth > 2*log2(n):     -> heapsort           # worst-case guard (introsort)
  pivot = median-of-three (or ninther for large size)       # avoid sorted-input O(n^2)
  if partition produced a near-extreme split:
        shuffle a few elements                               # break adversarial patterns (pdqsort)
  if many elements equal the pivot:   -> three-way partition # duplicate-key guard
  else:                               -> block partition     # branchless hot path
  recurse smaller side, loop larger                          # O(log n) stack

Every branch addresses a specific failure mode covered in this file: insertion-sort for overhead, heapsort for the O(n²) tail, median-of-three for sorted input, pattern-breaking for adversaries, three-way for duplicates, block partition for branch misprediction, and tail-call elimination for stack depth. A "simple quicksort" omits all of these and is correct but production-unsafe.

4.2 Case study: the JDK dual-pivot adoption¶

JDK 7 (2009) replaced the single-pivot quicksort in Arrays.sort for primitives with Yaroslavskiy's dual-pivot scheme after benchmarks showed a consistent speedup. The interesting senior lesson is process: the change was driven by measurement, not asymptotic analysis (both are O(n log n)); the win was in constant factors — fewer cache misses from the three-region single pass. It also illustrates a maintenance hazard: dual-pivot, like all quicksorts, is O(n²) in the worst case, and a 2015 report showed certain inputs degrading JDK sort, prompting a documented input-size threshold and review. The takeaway: constant-factor sort optimizations are real and worth shipping, but the worst-case guard and adversarial testing must travel with them.

5. Engineering the Partition¶

The partition loop is the hot path; its constant factor dominates wall-clock time.

5.1 Branch misprediction¶

The naive partition has a data-dependent branch (if a[j] <= pivot) that the CPU cannot predict on random data, costing a pipeline flush roughly half the time. On modern hardware this branch can dominate the cost.

5.2 Block partitioning (branchless)¶

BlockQuicksort (Edelkamp-Weiß, 2016), used inside pdqsort, removes the unpredictable branch. Instead of branching per element, it scans a fixed-size block and records, into a small buffer, the offsets of elements that need to move (using arithmetic instead of branches). Then it performs the swaps in a tight loop. This converts the unpredictable branch into predictable, vectorizable arithmetic and can roughly double throughput on random data.

5.3 Other partition-level levers¶

• Pivot as sentinel: placing the pivot so it bounds the scan lets you drop a bounds check in the inner loop — but only memory-safe if the comparator is consistent (Section 3.3).
• Avoiding the all-equal pathology: when a partition produces zero "greater" elements (a sign of many equal keys), switch to three-way partitioning for that range.
• Cache: the sequential scan is already cache-friendly; the main remaining cost is the branch, which is why branchless partitioning is the big modern win.
• Cutoff to insertion sort: for ≤ ~16 elements, the simple O(k²) insertion sort beats partitioning overhead and is branch-light on nearly-sorted data.

6. Quickselect in Production¶

Selection (median, percentiles, top-k) is quickselect, and it has the same adversary problem as sorting.

6.1 Introselect¶

std::nth_element is introselect: quickselect with a fallback to median-of-medians (or heapselect) when recursion goes too deep, guaranteeing worst-case O(n). The common path uses a cheap random/median-of-three pivot (expected O(n), small constant); the guard only engages on pathological inputs.

6.2 Top-k: select vs heap¶

For "top k of n", there are two regimes:

• k small relative to n: a bounded min-heap of size k is O(n log k) and streaming-friendly (no need to hold all n in memory, no mutation of input).
• k comparable to n, all data in memory: quickselect to partition around rank k, then the first k elements are the answer — expected O(n), but it mutates the array and needs all data present.

Choosing between them is a senior data-shape decision: heap for streaming / small k / immutable input; quickselect for in-memory / large k / mutation allowed.

6.3 Median-of-medians caveat¶

Median-of-medians guarantees O(n) worst case but has a large constant (it recursively selects the median of ⌈n/5⌉ group-medians). In practice it is slower than randomized quickselect on almost all inputs, so it is used as a guard (introselect), not as the primary path — exactly the introsort pattern applied to selection.

6b. Cache, Memory, and Parallel Quicksort¶

6b.1 Why quicksort beats heapsort in wall-clock time¶

Both are O(n log n), but quicksort's partition scan is sequential — it walks the subarray front-to-back (Lomuto) or from both ends inward (Hoare), reading contiguous cache lines. Heapsort, by contrast, sifts elements up and down a binary heap, jumping between indices i, 2i+1, 2i+2 that are far apart in memory, thrashing the cache. On modern hardware the memory hierarchy, not the comparison count, dominates, so quicksort's locality gives it a 2–3× wall-clock edge over heapsort despite identical asymptotics. This is precisely why introsort uses quicksort as the common path and heapsort only as a guard.

6b.2 In-place is a memory-bandwidth advantage¶

Merge sort's O(n) scratch array doubles the working set and the memory traffic (read input, write scratch, copy back). Quicksort's in-place partition touches each element a small number of times within the array it already occupies, halving memory traffic. For large n that do not fit in cache, this is a real throughput difference, not just a O(1) vs O(n) space footnote.

6b.3 Parallel quicksort¶

Quicksort parallelizes naturally because the two subproblems after a partition are independent (disjoint index ranges, no shared mutable state). The standard pattern:

• Partition sequentially (the partition itself is hard to parallelize cheaply — it has a sequential data dependency).
• Fork the two recursive calls onto a task pool / work-stealing scheduler (e.g. ForkJoinPool, Go goroutines, Rust rayon).
• Stop forking below a grain size (e.g. ranges < 8192) and sort sequentially, so task-creation overhead does not dominate.

The speedup is bounded by Amdahl's law: the top-level partition is sequential O(n), so the best achievable parallel time is O(n) (the first partition) + O(n/p · log n) for the parallel subtrees. Parallel partitioning (prefix-sum-based) can break the top-level sequential bottleneck for very large n, but adds complexity; most libraries parallelize only the recursion, not the partition.

6b.4 External (on-disk) sorting¶

Quicksort is a poor fit for data too large for RAM, because its random-ish access pattern across the whole array causes catastrophic disk seeking. External merge sort is the standard choice there: it streams sequential runs, sorts each in memory, and merges them with sequential I/O. The takeaway: quicksort's locality wins inside the cache hierarchy but loses at the disk boundary, where merge sort's sequential streaming dominates — the same trade-off that makes merge sort the right tool for linked lists and stable sorts.

7. Code Examples¶

7.1 Go — introsort (quicksort + heapsort guard + insertion cutoff)¶

package main

import (
    "fmt"
    "math/bits"
)

const cutoff = 16

func insertionSort(a []int, lo, hi int) {
    for i := lo + 1; i <= hi; i++ {
        v, j := a[i], i-1
        for j >= lo && a[j] > v {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = v
    }
}

func siftDown(a []int, lo, hi, root int) {
    n := hi - lo + 1
    for {
        child := 2*(root-lo) + 1 + lo
        if child-lo >= n {
            break
        }
        if child+1-lo < n && a[child+1] > a[child] {
            child++
        }
        if a[root] >= a[child] {
            break
        }
        a[root], a[child] = a[child], a[root]
        root = child
    }
}

func heapsort(a []int, lo, hi int) {
    n := hi - lo + 1
    for i := lo + n/2 - 1; i >= lo; i-- {
        siftDown(a, lo, hi, i)
    }
    for end := hi; end > lo; end-- {
        a[lo], a[end] = a[end], a[lo]
        siftDown(a, lo, end-1, lo)
    }
}

func medianOfThree(a []int, lo, hi int) int {
    mid := lo + (hi-lo)/2
    if a[mid] < a[lo] {
        a[lo], a[mid] = a[mid], a[lo]
    }
    if a[hi] < a[lo] {
        a[lo], a[hi] = a[hi], a[lo]
    }
    if a[hi] < a[mid] {
        a[mid], a[hi] = a[hi], a[mid]
    }
    a[mid], a[hi] = a[hi], a[mid] // median to hi for Lomuto
    return a[hi]
}

func partition(a []int, lo, hi int) int {
    pivot := medianOfThree(a, lo, hi)
    i := lo - 1
    for j := lo; j < hi; j++ {
        if a[j] <= pivot {
            i++
            a[i], a[j] = a[j], a[i]
        }
    }
    a[i+1], a[hi] = a[hi], a[i+1]
    return i + 1
}

func introsortRec(a []int, lo, hi, depthLimit int) {
    for hi-lo > cutoff {
        if depthLimit == 0 {
            heapsort(a, lo, hi) // worst-case guard
            return
        }
        depthLimit--
        p := partition(a, lo, hi)
        introsortRec(a, p+1, hi, depthLimit) // recurse one side
        hi = p - 1                            // loop the other
    }
    insertionSort(a, lo, hi)
}

func Introsort(a []int) {
    if len(a) < 2 {
        return
    }
    depthLimit := 2 * bits.Len(uint(len(a))) // ~2*floor(log2 n)
    introsortRec(a, 0, len(a)-1, depthLimit)
}

func main() {
    a := []int{5, 3, 8, 1, 9, 2, 7, 4, 6, 0, 5, 5, 3, 8, 1, 9, 2, 7, 4}
    Introsort(a)
    fmt.Println(a)
}

7.2 Java — randomized quickselect (top-k via nth_element style)¶

import java.util.Random;

public class QuickSelect {
    static final Random rng = new Random();

    // Rearranges a so that a[k] holds the (k+1)-th smallest, and
    // a[0..k-1] are all <= a[k] <= a[k+1..]. Expected O(n).
    static void nthElement(int[] a, int k) {
        int lo = 0, hi = a.length - 1;
        while (lo < hi) {
            int r = lo + rng.nextInt(hi - lo + 1);
            int t = a[r]; a[r] = a[hi]; a[hi] = t;
            int pivot = a[hi], i = lo - 1;
            for (int j = lo; j < hi; j++)
                if (a[j] <= pivot) { i++; int s = a[i]; a[i] = a[j]; a[j] = s; }
            i++;
            int s = a[i]; a[i] = a[hi]; a[hi] = s;
            if (k == i) return;
            else if (k < i) hi = i - 1;
            else lo = i + 1;
        }
    }

    public static void main(String[] args) {
        int[] a = {9, 1, 8, 2, 7, 3, 6, 4, 5};
        int k = 3;                         // want the 4 smallest (ranks 0..3)
        nthElement(a, k);
        // a[0..k] now contains the k+1 smallest, unsorted among themselves
        System.out.printf("element of rank %d = %d%n", k, a[k]); // 4
    }
}

7.3 Python — pdqsort-style: detect already-sorted / break bad patterns¶

import random

CUTOFF = 16


def insertion_sort(a, lo, hi):
    for i in range(lo + 1, hi + 1):
        v, j = a[i], i - 1
        while j >= lo and a[j] > v:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = v


def median_of_three(a, lo, hi):
    mid = (lo + hi) // 2
    if a[mid] < a[lo]:
        a[lo], a[mid] = a[mid], a[lo]
    if a[hi] < a[lo]:
        a[lo], a[hi] = a[hi], a[lo]
    if a[hi] < a[mid]:
        a[mid], a[hi] = a[hi], a[mid]
    a[mid], a[hi] = a[hi], a[mid]
    return a[hi]


def partition(a, lo, hi):
    pivot = median_of_three(a, lo, hi)
    i = lo - 1
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1


def pdq(a, lo, hi, depth_limit):
    while hi - lo > CUTOFF:
        if depth_limit == 0:
            # worst-case guard: fall back to heapsort on this range
            import heapq
            sub = a[lo:hi + 1]
            heapq.heapify(sub)
            for idx in range(lo, hi + 1):
                a[idx] = heapq.heappop(sub)
            return
        depth_limit -= 1
        p = partition(a, lo, hi)
        # detect a highly unbalanced split → shuffle to break the pattern
        if min(p - lo, hi - p) < (hi - lo) // 8:
            mid = (lo + hi) // 2
            a[lo], a[random.randint(lo, hi)] = a[random.randint(lo, hi)], a[lo]
            a[mid], a[random.randint(lo, hi)] = a[random.randint(lo, hi)], a[mid]
        pdq(a, lo, p - 1, depth_limit)
        lo = p + 1
    insertion_sort(a, lo, hi)


def pdqsort(a):
    if len(a) < 2:
        return
    depth_limit = 2 * a.__len__().bit_length()
    pdq(a, 0, len(a) - 1, depth_limit)


if __name__ == "__main__":
    a = list(range(40))        # already sorted: pattern-defeating still O(n log n)
    random.shuffle(a)
    pdqsort(a)
    assert a == list(range(40))
    print("sorted ok")

8. Observability and Testing¶

A sort result is easy to verify (is it ordered? is it a permutation of the input?), but the performance pathologies are silent. Build in checks.

The single most valuable test is the multiset-permutation + sorted check against the language's built-in sort on randomized inputs, including the adversarial families above. The second most valuable is a depth/comparison-count gauge wired into metrics, so a sudden quadratic blowup in production is observable rather than just "the service got slow."

8.1 A property-test battery¶

for random input (including sorted, reverse, all-equal, few-distinct, organ-pipe):
    b := copy(input); mysort(b)
    assert is_sorted(b)
    assert multiset(b) == multiset(input)          # permutation invariant
    assert b == sorted(input)                       # oracle: built-in sort
    assert recursion_depth <= 2*ceil(log2 n) + C   # introsort guard
for the McIlroy killer adversary:
    assert comparison_count(mysort) == O(n log n)   # not O(n^2)

8.2 Production guardrails¶

For a service that sorts untrusted input: seed the pivot RNG from an unpredictable source (so an attacker cannot replay it); enforce the introsort depth limit so the worst case is O(n log n) regardless; emit comparison-count and max-depth metrics per large sort so anomalies are visible; and validate user comparators (or use a memory-safe partition) to avoid out-of-bounds reads on a broken cmp.

8.3 SLOs and capacity for a sort-heavy service¶

If sorting (or selection) sits on a latency-critical path, treat it like any other capacity concern:

• Define the SLO on the guaranteed bound, not the average. Because plain quicksort's tail is O(n²), a p99.9 latency SLO is only defensible if you run introsort (deterministic O(n log n)). Otherwise a single adversarial or unlucky input blows the budget.
• Cap input size. An O(n log n) sort on an unbounded user-supplied list is a memory-and-CPU amplification vector. Enforce a maximum n, and stream/paginate beyond it.
• Pre-check for cheap wins. Real data is often already sorted or nearly so; a pre-scan that detects sortedness (O(n)) lets pdqsort-style code short-circuit, and is a legitimate SLO optimization for append-mostly datasets.
• Budget the comparator. With user-supplied comparators, the per-comparison cost is unbounded; the sort does Θ(n log n) comparisons, so a slow comparator multiplies through. Profile the comparator separately from the sort.

8.4 Reproducibility vs attack resistance¶

The randomized pivot creates a tension: randomness defeats adversaries (Section 3) but makes runs non-deterministic, complicating debugging and golden-output tests. Resolve it with environment-dependent seeding: a fixed seed in CI/replay (deterministic, reproducible test failures) and an unpredictable seed in production (attack-resistant). The seed is the single knob that trades these properties; expose it in configuration and log it (in non-adversarial contexts) so a slow sort can be reproduced.

9. Failure Modes¶

9.1 Quadratic blowup on adversarial input¶

A deterministic pivot (first/last/median-of-three) lets an attacker force O(n²) (McIlroy killer). Mitigation: randomized pivot plus introsort depth guard.

9.2 Stack overflow on bad splits¶

Recursing both sides without small-side-first lets depth reach O(n). Mitigation: recurse the smaller partition, loop (tail-call) on the larger — depth O(log n).

9.3 All-equal / few-distinct pathology¶

Two-way partitioning is O(n²) on many equal keys. Mitigation: three-way (Dutch National Flag) partition, or detect a degenerate split and switch.

9.4 Broken comparator → out-of-bounds¶

An inconsistent comparator can drive an optimized Hoare loop past the array bounds (memory unsafety) or throw. Mitigation: bounds-checked partition, or validate the strict-weak-ordering contract (Java's approach).

9.5 Relying on stability¶

Quicksort reorders equal elements; code that assumed stable order silently breaks. Mitigation: use a stable sort (merge/TimSort) when order of equals matters, or tag elements with their index.

9.6 Wrong worst-case guarantee in a latency-critical path¶

Plain quicksort in a real-time path can miss a deadline on a O(n²) input. Mitigation: introsort (guaranteed O(n log n)) or heapsort if O(1) space and a hard worst-case bound are required.

9.7 Quickselect quadratic¶

Selection has the same O(n²) exposure as sorting. Mitigation: randomized pivot (expected O(n)) plus introselect's median-of-medians guard for worst-case O(n).

9.8 Non-determinism breaking reproducibility¶

A randomized pivot makes runs non-reproducible, which complicates debugging and testing. Mitigation: seed the RNG deterministically in test/replay environments (but unpredictably in production against adversaries) — the seed is the knob that trades reproducibility for attack resistance.

10. Summary¶

• Introsort is the production answer to the O(n²) worst case: quicksort for speed, a heapsort fallback triggered by a 2⌊log₂ n⌋ depth limit for the guarantee, and an insertion-sort cutoff for small ranges. The C++ standard mandates O(n log n), which is why std::sort is introsort, not plain quicksort.
• Adversarial inputs are a security issue. A deterministic pivot is attackable (McIlroy's killer forces O(n²)). Defend with randomization (makes targeting infeasible) plus the introsort depth guard (bounds the damage). Algorithmic-complexity DoS is mitigated by both unpredictability and a guaranteed fallback.
• Standard libraries are hybrids: introsort (std::sort), dual-pivot quicksort (Java primitives), pdqsort (Rust/Go unstable sort), introselect (std::nth_element). Stable sorts (TimSort, Java object sort) avoid quicksort because it is not stable.
• The partition is the hot path. The big modern win is branchless / block partitioning (BlockQuicksort, inside pdqsort), which removes the unpredictable a[j] <= pivot branch. Three-way partitioning guards the duplicate-key pathology; insertion-sort cutoffs handle small ranges.
• Quickselect powers median/percentile/top-k in expected O(n); introselect adds a median-of-medians guard for worst-case O(n). Choose a heap for streaming/small-k/immutable input, quickselect for in-memory/large-k/mutable.
• Observe and test: verify sorted-ness and the permutation invariant against a built-in oracle; wire up recursion-depth and comparison-count metrics; test the adversarial families (sorted, reverse, all-equal, few-distinct, organ-pipe, McIlroy killer); validate comparators.

Decision summary¶

• General in-memory sort, untrusted input → introsort (randomized + depth guard).
• Stability required → merge sort / TimSort, not quicksort.
• Hard worst-case O(n log n), O(1) space → heapsort.
• Median / percentile / top-k, in memory → quickselect / introselect.
• Top-k, streaming or immutable input → bounded heap, O(n log k).
• Many duplicate keys → three-way (Dutch National Flag) partition.
• Hot loop, random data → branchless / block partitioning.

References to study further: Musser's Introspective Sorting and Selection Algorithms (1997); McIlroy's A Killer Adversary for Quicksort (1999); Yaroslavskiy's dual-pivot quicksort; Peters' pdqsort (2014); Edelkamp-Weiß BlockQuicksort (2016); BFPRT median-of-medians (1973); Crosby-Wallach on algorithmic complexity attacks (2003); and sibling topics 01-merge-sort, 03-heapsort.