Sorting: Comparison, Radix & Hybrid Schemes

Sorting is a transformation that establishes an order contract. It is useful not because an ascending list looks tidy, but because it enables binary search, range scans, duplicate grouping, merge joins, deterministic presentation, and simple downstream invariants. Before choosing an algorithm, decide what “ordered” means, whether equal records must retain their order, whether the input can fit in memory, and whether a rare quadratic case is acceptable.

The elementary insertion, selection, exchange, shaker, and Shell variants in the supplied book are useful first mechanisms. They are not a production selection rule by themselves. Modern libraries use hybrids because data shape, comparison cost, memory, and tail risk matter together.

State the order contract first #

Let less(a, b) mean “a must appear before b.” A general-purpose comparison sort requires a strict weak ordering: it is irreflexive (less(x,x) is false), transitive, and induces transitive equivalence where neither value is less than the other. A comparator based on mutable time, inconsistent floating-point rules, or non-transitive “preference” is not a difficult input; it breaks the precondition.

For example, first stable-sort people by given name, then stable-sort by family name. Within each family name, the earlier given-name order remains. An unstable sort may be perfectly correct for the key order while destroying that presentation property.

Why comparison sorting has an $\Omega(n\log n)$ floor #

For $n$ distinct items, a comparison sort must distinguish among $n!$ possible input orders. Its comparisons form a decision tree: an internal node asks one binary question and a leaf chooses an output order. A binary tree of height $h$ has at most $2^h$ leaves, so correctness requires

$$2^h\ge n!\quad\Longrightarrow\quad h\ge \log_2(n!)=\Omega(n\log n).$$

This is a lower bound on comparisons for a general comparison model, not a universal ban on linear sorting. If a key has inspectable digits from a bounded alphabet, radix or counting passes obtain more information per operation than less(a,b). If most input is already ordered, an adaptive comparison sort can also use fewer comparisons on that particular input while retaining an $O(n\log n)$ worst case.

Elementary sorts teach different invariants #

Insertion sort: a sorted prefix grows #

After processing position i, insertion sort maintains that a[0:i] is sorted and contains exactly the original first i elements. It removes a[i], shifts the larger prefix elements one slot right, then inserts the saved value in the gap.

def insertion_sort(a, less):
    for i in range(1, len(a)):
        item = a[i]
        j = i
        while j > 0 and less(item, a[j - 1]):
            a[j] = a[j - 1]
            j -= 1
        a[j] = item

The assignment a[j] = item happens only after the hole has been found, so the algorithm does not lose the extracted element. It is stable when equal items are not shifted past each other. Worst-case time is $\Theta(n^2)$, but nearly sorted short runs need few shifts; that is why hybrids commonly use it below a small partition threshold.

Selection sort instead fixes the next output position by scanning the remainder for its minimum. It always makes $\Theta(n^2)$ comparisons but only $O(n)$ swaps. That distinction can matter for unusually expensive writes, though ordinary implementations should still be measured rather than chosen from asymptotics alone.

Divide, merge, and partition #

Merge sort recursively sorts two halves and merges their sorted outputs. Its merge invariant is: after emitting $k$ values, the output prefix contains the $k$ smallest values from both input prefixes in sorted order. It is stable when equal keys choose from the left run first. Time is $O(n\log n)$ in every case; a straightforward in-memory version needs $O(n)$ auxiliary storage. Its sequential merge access is also the basis of external sorting.

Quicksort chooses a pivot, partitions values into regions relative to it, and recursively sorts the regions. The partition boundary is powerful because it needs little extra storage and has good average behavior, but unbalanced pivots can leave a subproblem of size $n-1$, producing $\Theta(n^2)$ work and deep recursion. Hoare's original paper introduced the method; a production implementation must additionally specify pivot policy, equal-key handling, recursion strategy, and a worst-case guard.

For duplicate-heavy data, use a three-way partition:

[ values < pivot | values equivalent to pivot | values > pivot ]
                 ^ no recursive work on this region ^

The invariant gives equal keys a terminal region instead of repeatedly feeding them into one recursive side. It also makes the comparator's equivalence relation operationally visible.

Heapsort builds a binary heap, repeatedly extracts the extreme value, and needs $O(1)$ auxiliary element storage with $O(n\log n)$ worst-case time. It is normally unstable and its access pattern often has less favorable locality than a well-engineered quicksort, but its bound makes it an excellent fallback.

Introsort: optimize the common case without giving up the bound #

Musser's introspective sort starts with quicksort and tracks partition depth. If the depth exceeds a limit proportional to $\log n$, it switches to heapsort; small partitions use insertion sort. This creates three regimes:

It is a pattern, not a required exact implementation. The C++ standard specifies the complexity contract of sort, not a single algorithm, so callers should rely on guarantees rather than reverse-engineering a vendor's current hybrid. If stability is required, request a stable sorting API explicitly; the C++ draft defines stable sort separately and permits an implementation to trade extra memory for different comparison bounds.

Radix sorting escapes the comparison model #

For keys decomposable into $d$ digits from an alphabet of size $r$, least-significant-digit radix sorting performs stable passes from the least significant digit to the most significant. A counting-style pass costs $O(n+r)$, so total work is

$$O(d(n+r)).$$

Stability is essential: after sorting by a more significant digit, equal values of that digit must retain the order established by less significant passes. Fixed-width 32-bit integers can use, for example, four byte-wide passes ($d=4$, $r=256$); variable-length strings and huge sparse alphabets require a more careful cost model.

Do not say “radix sort is linear” without its parameters. When $r$ is enormous relative to $n$, clearing and scanning a counting array can dominate. When the key is a record field, specify byte order, signed-value transform, Unicode normalization, and whether the desired order is lexical, numeric, or locale-aware.

A practical selection guide #

The first row is intentionally “library sort,” not a handwritten quicksort. Libraries encode years of work on pivoting, duplicate patterns, stack discipline, move semantics, adversarial cases, and hardware behavior. Handwrite one only when the problem adds a verified requirement the library contract cannot express.

Failure modes that look like sorting bugs #

1. Comparator is not an ordering. Log a small cycle such as a<b, b<c, c<a; no comparison sort can produce a coherent result.
2. Equal means different things. Sorting by a key but then grouping by full-record equality causes apparent duplicate failures.
3. Stability was assumed, not requested. Include an original position tie-breaker or use a stable operation.
4. Sort key changes during the operation. Snapshot keys or synchronize; otherwise the output cannot satisfy one fixed ordering.
5. Full sort used for a boundary query. A partial selection followed by local sorting can be the correct lower-work plan.
6. Benchmark excludes key extraction and allocation. Measure end-to-end data movement, allocations, and comparison cost on representative distributions.

Exercises #

1. Explain why a stable sort of (team, arrival) records by team preserves arrival order within each team, while an unstable correct sort need not.
2. A quicksort partition produces regions of sizes 1 and $n-1$ at every recursion. Give its recurrence and asymptotic time.