Sorting

The five

*Quicksort's O(n²) worst case requires pathologically bad pivots; modern implementations use random or median-of-three pivots to make it astronomically rare.

The two that matter — quicksort and mergesort

Quicksort picks a pivot, partitions the data into "less than pivot" and "greater than pivot", recurses on each. Beautifully simple, fast in practice, in-place. Its worst case is bad but practically unreachable with reasonable pivot selection.

// quicksort sketch
void quicksort(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(v, lo, hi);
    quicksort(v, lo, p - 1);
    quicksort(v, p + 1, hi);
}

Mergesort splits the array in half, recursively sorts each half, merges them back together. Always O(n log n) — no bad cases. Stable (preserves relative order of equal elements). Needs O(n) auxiliary memory for the merge step. The default for sorting linked lists, external sorting (data on disk), and stable in-memory sorts.

What std::sort actually does

Modern std::sort implementations use a hybrid called introsort: start with quicksort, switch to heapsort if recursion goes too deep (avoiding the O(n²) worst case), and use insertion sort for small partitions where it's fastest. Three algorithms in a trench coat, doing the right thing at every scale.

The result: O(n log n) guaranteed worst case, very fast in practice, in-place. Usable for almost any sorting need without thought. Don't write your own sort. The standard library spent decades getting this right.

When you'd choose differently

• Tiny arrays (≤ ~16 elements): insertion sort. The constants are smaller than quicksort's overhead.
• Already-sorted or nearly-sorted data: Tim sort (Python's sorted). Detects existing runs.
• External (on-disk) data: mergesort. Reads sequentially, writes sequentially.
• Sorting integers in a small range: radix sort or counting sort. O(n), beats comparison-based sorts.
• Need stability: std::stable_sort. Slightly slower but preserves relative order.

Most of the time, none of these come up. Use std::sort.

Why this matters for AI

Top-K selection — picking the K best logits from a probability distribution at each token — is technically O(n) (you don't need to fully sort), but partial sorts and quickselect are still in the inner loop of every language model's sampling code. std::partial_sort handles it.

Sorting also appears in dataset preprocessing (deduplicating training data is a sort + scan), in evaluation (ranking model outputs), and in indexing (vector databases use sort+search throughout).

Use the library. Forty years of algorithmic engineering is already in there.

What's next

Week 34 is Linked Lists — the data structure that pointers were invented for, and the lessons learned from forty years of "should I use one of these?".