Capstone: A Sorting Library With Benchmarks
Module 2 taught you five sorting algorithms one lesson at a time. This capstone puts them side by side in one small library, with one interface, one test harness and one benchmark, so that the claims from those lessons become numbers you measured yourself. "Insertion sort is fast on nearly sorted data", "quicksort is fast on average but has a quadratic worst case", "radix sort beats " — by the end you will know how much faster, on which inputs, and why the measurements sometimes disagree with the textbook.
You will build: insertion sort, a merge sort with a single auxiliary buffer, a quicksort that falls back to heap sort when its recursion gets too deep (introsort, the algorithm inside C++'s std::sort), heap sort, and an LSD radix sort for 32-bit integers. Then you will stress-test all five against your language's built-in sort and benchmark them on four input shapes.
Goal
When you finish you will have:
- A module exposing five sorts with the same signature: take a mutable array of 32-bit signed integers and sort it in place in ascending order.
- A differential test harness that runs every sort on hand-picked edge cases and hundreds of random arrays and compares the result with the built-in sort.
- A benchmark that times every sort (plus the built-in) on random, sorted, reversed and few-unique inputs at several sizes, and prints a table.
- A one-page write-up explaining the table in terms of comparisons, data movement, adaptivity and cache behaviour.
Requirements
- Interface. Every sort is a function
sort(a)that mutatesaand returns nothing. Register them in one table (name → function) so the tests and the benchmark iterate over the table, not over hard-coded calls. Adding a sixth algorithm should be a one-line change. - Element type. 32-bit signed integers, including
-2^31and2^31 - 1.- Insertion sort must also accept a sub-range[lo, hi], because merge sort and introsort reuse it for small ranges. - Merge sort allocates one auxiliary buffer of size once, not one per call, cuts over to insertion sort below 16 elements, and skips the merge when the two halves are already in order.
- Quicksort / introsort: median-of-three pivot, a partition that splits evenly on all-equal input, recursion on the smaller side and iteration on the larger (stack depth ), insertion sort below 16 elements, and a depth budget of after which the current range is finished with heap sort. Worst case .
- Heap sort must work on a sub-range
[lo, hi]so introsort can call it. - Radix sort: LSD, base 256, four stable counting passes, correct for negative numbers.
- Correctness first. Tests assert only correctness. Timing is printed, never asserted: timings vary across machines and runs, and a test that fails because the laptop was busy teaches nothing.
Staged plan
flowchart LR
P1["Part 1<br/>interface, insertion sort,<br/>test harness"] --> P2["Part 2<br/>merge sort"]
P2 --> P3["Part 3<br/>heap sort on a range"]
P3 --> P4["Part 4<br/>quicksort + introsort fallback"]
P4 --> P5["Part 5<br/>radix sort"]
P5 --> P6["Part 6<br/>benchmark"]
P6 --> P7["Part 7<br/>write-up"]
Part 1 — the interface, insertion sort and the harness
Write the registry and the simplest sort first, then the harness, before any fast algorithm exists. The harness is what lets you write the hard sorts quickly, because it tells you within a second when you have broken something. This is differential testing from Testing & Debugging Algorithms: the built-in sort is the oracle.
The harness runs each registered sort on a copy of every test array and compares with the built-in result. Use small random arrays (length 0–200, values in a narrow range like so duplicates are common) and a fixed seed so failures are reproducible. When a test fails, print the smallest failing input you can find; shrinking a failing case by hand from 200 elements to 5 is where most of the debugging insight comes from.
Insertion sort: for each i, save a[i], shift larger elements of a[lo..i-1] one slot right, drop the saved value into the gap. It is stable, in place, and does work, which is why it is the base case of every serious hybrid sort (Elementary Sorts & Stability).
Part 2 — merge sort with one buffer
Top-down merge sort on [lo, hi]: sort both halves, then merge through the buffer. Three engineering details from Merge Sort & Inversion Counting turn the textbook version into a fast one:
- One buffer. Allocate
bufof length once. Allocating inside each call costs allocations and dominates the run time in garbage-collected languages. - Insertion-sort cutoff. Below about 16 elements, insertion sort's tiny constant beats merge sort's overhead.
- Skip sorted merges. If
a[mid] <= a[mid + 1]after sorting both halves, the range is already sorted; return. This one line makes merge sort run in on already-sorted input.
Keep the merge stable: on ties, take from the left half.
Part 3 — heap sort on a sub-range
Implement heap_sort(a, lo, hi): build a max-heap over the range with bottom-up sift-down (in ), then repeatedly swap the root to the end and sift down the shrunk heap. All index arithmetic is relative to lo: the children of relative index are and , stored at a[lo + 2r + 1] and a[lo + 2r + 2]. Test it alone through the registry first, as a full-array sort; introsort will call it on sub-ranges later (Heap Sort).
Part 4 — quicksort with an introsort fallback
This is the centre of the project, and it follows Quick Sort, Partition Schemes & Introsort.
flowchart TD
S["intro(a, lo, hi, depth)"] --> Q{"range size < 16?"}
Q -->|"yes"| I["insertion sort a[lo..hi]"]
Q -->|"no"| D{"depth == 0?"}
D -->|"yes"| H["heap sort a[lo..hi]<br/>guaranteed n log n"]
D -->|"no"| P["depth = depth - 1<br/>pivot = median of a[lo], a[mid], a[hi]"]
P --> T["Hoare-style partition:<br/>a[lo..j] at most pivot, a[i..hi] at least pivot"]
T --> R["recurse on the smaller side,<br/>loop on the larger side"]
R --> Q
- Partition. Use the crossing-pointers scheme:
imoves right whilea[i] < pivot,jmoves left whilea[j] > pivot, swap and step both wheni <= j. Both pointers stop on elements equal to the pivot, so an all-equal array is split down the middle instead of degenerating. (Lomuto partition with "<=goes left" is quadratic on all-equal input; try it and watch the harness time out.) - Smaller side first. Recurse into the smaller of
[lo, j]and[i, hi]and continue the loop on the larger. Each recursive call is on at most half the range, so the stack never exceeds frames even when the partitions are lopsided. - The depth budget. Start with
depth = 2 * floor(log2(n))and decrement it on each partition. If it reaches zero, finish the current range with heap sort. Random and ordinary inputs never get near the budget; adversarial inputs (such as Musser's "median-of-3 killer" sequences) do, and the fallback caps the total at . - How to test the fallback. Call the internal routine with
depth = 0directly: it must still sort correctly, because then it is pure heap sort on the range. Without this test the fallback path is dead code that nobody ever runs.
Part 5 — LSD radix sort for 32-bit integers
Four passes of stable counting sort, one per byte, least significant byte first (Non-Comparison Sorts & the Lower Bound). Each pass: count the 256 byte values, turn the counts into starting offsets by a prefix sum, then scatter elements into an output array in input order (stability is what makes later passes preserve earlier ones). Swap input and output and repeat.
Negative numbers. In two's complement, negative numbers have the top bit set, so sorting by unsigned bytes would put them after the positives. Flip the sign bit before extracting digits: key = x XOR 0x80000000 maps monotonically onto . In Python, whose integers are unbounded, use x + 2**31 instead.
Radix sort does scatter writes regardless of input order, so expect it to be flat across all four input shapes.
Part 6 — benchmark
Generate four input shapes at each size :
| Shape | Construction | What it exposes |
|---|---|---|
| Random | uniform 32-bit integers | the average case |
| Sorted | 0, 1, …, n-1 | adaptivity (insertion and merge with the skip check should be near ) |
| Reversed | n, n-1, …, 1 | the worst case for insertion sort; a classic trap for naive quicksort pivots |
| Few unique | uniform over | duplicate handling in partitions |
Measurement rules, from Benchmarks and the Module 0 capstone: generate the data outside the timed region; time each sort on a fresh copy (sorting already-sorted output measures the wrong thing); repeat at least 3–5 times and report the minimum or median; warm up JIT runtimes (Java, Node) before measuring; verify the output after timing so a broken sort cannot win. Run insertion sort only at small — at reversed it would take hours in Python.
Report a table per size: rows are algorithms, columns are input shapes, cells are milliseconds. Include the built-in sort as the last row.
Part 7 — write-up
One page answering: Which algorithm won on each shape, and why? Where did the measured ratio between two sorts come from (comparisons? data movement? cache misses? interpreter overhead)? How far is your best sort from the built-in, and what is the built-in doing that you are not (Sorting in the Real World)? At what does radix sort start beating your fastest comparison sort?
Acceptance tests
Every registered sort must produce exactly the built-in result on all of these:
| # | Input | Why it is here |
|---|---|---|
| 1 | [] | empty range; off-by-one in hi = n - 1 |
| 2 | [1] | single element |
| 3 | [2, 1] | smallest swap |
| 4 | [3, -1, 2, -1, 0] | negatives and a duplicate |
| 5 | fifty copies of 5 | all equal: partition balance, merge stability |
| 6 | [2147483647, -2147483648, 0, -1, 1] | extremes: overflow in median-of-three or in radix keys |
| 7 | 0 … 999 | sorted: adaptivity, naive pivots |
| 8 | 1000 … 1 | reversed |
| 9 | i % 3 for i in 0 … 499 | few unique |
| 10 | 300 random arrays, length 0–200, values in , fixed seed | everything else |
| 11 | introsort internal routine with depth = 0 on cases 1–10 | the heap-sort fallback path actually runs |
And a performance sanity check (printed, not asserted): at , every sort except insertion should finish each shape in well under a second even in Python; insertion sort on reversed input should be the slowest cell in the table by a wide margin.
Reference solution
Try Parts 1–5 yourself first. Each reference program below contains all five sorts, the registry, the acceptance tests and a small benchmark (n = 2000, best of 3) that prints a table. Raise BENCH_N and drop insertion sort from the registry for real measurements.
Reference solution: sorting library in four languages
import random
import time
# ---------- the five sorts: each sorts list[int] in place ----------
def insertion_sort(a: list[int], lo: int = 0, hi: int | None = None) -> None:
if hi is None:
hi = len(a) - 1
for i in range(lo + 1, hi + 1):
x = a[i]
j = i - 1
while j >= lo and a[j] > x:
a[j + 1] = a[j]
j -= 1
a[j + 1] = x
def merge_sort(a: list[int]) -> None:
buf = a[:] # one auxiliary buffer
def rec(lo: int, hi: int) -> None:
if hi - lo < 16:
insertion_sort(a, lo, hi)
return
mid = (lo + hi) // 2
rec(lo, mid)
rec(mid + 1, hi)
if a[mid] <= a[mid + 1]: # halves already in order
return
buf[lo:hi + 1] = a[lo:hi + 1]
i, j = lo, mid + 1
for k in range(lo, hi + 1):
if i > mid:
a[k] = buf[j]; j += 1
elif j > hi:
a[k] = buf[i]; i += 1
elif buf[j] < buf[i]: # strict: ties take the left (stable)
a[k] = buf[j]; j += 1
else:
a[k] = buf[i]; i += 1
rec(0, len(a) - 1)
def heap_sort(a: list[int], lo: int = 0, hi: int | None = None) -> None:
if hi is None:
hi = len(a) - 1
n = hi - lo + 1
def sift(root: int, size: int) -> None:
while True:
child = 2 * root + 1
if child >= size:
return
if child + 1 < size and a[lo + child + 1] > a[lo + child]:
child += 1
if a[lo + root] >= a[lo + child]:
return
a[lo + root], a[lo + child] = a[lo + child], a[lo + root]
root = child
for r in range(n // 2 - 1, -1, -1):
sift(r, n)
for end in range(n - 1, 0, -1):
a[lo], a[lo + end] = a[lo + end], a[lo]
sift(0, end)
def _intro(a: list[int], lo: int, hi: int, depth: int) -> None:
while hi - lo >= 16:
if depth == 0:
heap_sort(a, lo, hi) # fallback: guaranteed n log n
return
depth -= 1
mid = (lo + hi) // 2
p = sorted((a[lo], a[mid], a[hi]))[1] # median of three
i, j = lo, hi
while i <= j:
while a[i] < p:
i += 1
while a[j] > p:
j -= 1
if i <= j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
if j - lo < hi - i: # recurse on the smaller side
_intro(a, lo, j, depth)
lo = i
else:
_intro(a, i, hi, depth)
hi = j
insertion_sort(a, lo, hi)
def intro_sort(a: list[int]) -> None:
if len(a) > 1:
_intro(a, 0, len(a) - 1, 2 * (len(a).bit_length() - 1))
def radix_sort(a: list[int]) -> None:
src = a[:]
dst = [0] * len(a)
for shift in (0, 8, 16, 24):
count = [0] * 257
for x in src:
count[(((x + 2**31) >> shift) & 0xFF) + 1] += 1
for b in range(256):
count[b + 1] += count[b] # count[b] = first slot for byte b
for x in src:
b = ((x + 2**31) >> shift) & 0xFF
dst[count[b]] = x
count[b] += 1
src, dst = dst, src
a[:] = src
SORTS = {
"insertion": insertion_sort,
"merge": merge_sort,
"introsort": intro_sort,
"heap": heap_sort,
"radix": radix_sort,
}
# ---------- acceptance tests ----------
def fixed_cases() -> list[list[int]]:
return [[], [1], [2, 1], [3, -1, 2, -1, 0], [5] * 50,
[2**31 - 1, -2**31, 0, -1, 1],
list(range(1000)), list(range(1000, 0, -1)), [i % 3 for i in range(500)]]
def run_tests() -> None:
rng = random.Random(42)
rand = [[rng.randint(-1000, 1000) for _ in range(rng.randint(0, 200))] for _ in range(300)]
cases = fixed_cases() + rand
for name, sort in SORTS.items():
for arr in cases:
b = arr[:]
sort(b)
assert b == sorted(arr), (name, arr[:10])
for arr in cases: # test 11: the fallback path
b = arr[:]
if b:
_intro(b, 0, len(b) - 1, 0)
assert b == sorted(arr)
print("all acceptance tests passed")
# ---------- benchmark (printed, never asserted) ----------
BENCH_N = 2000
def make(shape: str, n: int, rng: random.Random) -> list[int]:
if shape == "random":
return [rng.randint(-2**31, 2**31 - 1) for _ in range(n)]
if shape == "sorted":
return list(range(n))
if shape == "reversed":
return list(range(n, 0, -1))
return [rng.randint(0, 9) for _ in range(n)]
def bench(n: int = BENCH_N, reps: int = 3) -> None:
rng = random.Random(1)
shapes = ["random", "sorted", "reversed", "few-unique"]
data = {s: make(s, n, rng) for s in shapes}
algos = dict(SORTS, builtin=lambda a: a.sort())
print(f"n = {n}, best of {reps}, milliseconds")
print(f"{'':12}" + "".join(f"{s:>12}" for s in shapes))
for name, sort in algos.items():
row = []
for s in shapes:
best = float("inf")
for _ in range(reps):
b = data[s][:]
t0 = time.perf_counter()
sort(b)
best = min(best, time.perf_counter() - t0)
assert b == sorted(data[s])
row.append(best * 1000)
print(f"{name:12}" + "".join(f"{ms:12.2f}" for ms in row))
run_tests()
bench()
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Random;
import java.util.function.Consumer;
public class SortLib {
// ---------- the five sorts: each sorts int[] in place ----------
static void insertionSort(int[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++) {
int x = a[i], j = i - 1;
while (j >= lo && a[j] > x) { a[j + 1] = a[j]; j--; }
a[j + 1] = x;
}
}
static void insertionSort(int[] a) { insertionSort(a, 0, a.length - 1); }
static void mergeSort(int[] a) {
int[] buf = new int[a.length]; // one auxiliary buffer
mergeRec(a, buf, 0, a.length - 1);
}
static void mergeRec(int[] a, int[] buf, int lo, int hi) {
if (hi - lo < 16) { insertionSort(a, lo, hi); return; }
int mid = (lo + hi) >>> 1;
mergeRec(a, buf, lo, mid);
mergeRec(a, buf, mid + 1, hi);
if (a[mid] <= a[mid + 1]) return; // halves already in order
System.arraycopy(a, lo, buf, lo, hi - lo + 1);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = buf[j++];
else if (j > hi) a[k] = buf[i++];
else if (buf[j] < buf[i]) a[k] = buf[j++]; // ties take the left (stable)
else a[k] = buf[i++];
}
}
static void heapSort(int[] a, int lo, int hi) {
int n = hi - lo + 1;
for (int r = n / 2 - 1; r >= 0; r--) sift(a, lo, r, n);
for (int end = n - 1; end > 0; end--) {
swap(a, lo, lo + end);
sift(a, lo, 0, end);
}
}
static void heapSort(int[] a) { heapSort(a, 0, a.length - 1); }
static void sift(int[] a, int lo, int root, int size) {
while (true) {
int child = 2 * root + 1;
if (child >= size) return;
if (child + 1 < size && a[lo + child + 1] > a[lo + child]) child++;
if (a[lo + root] >= a[lo + child]) return;
swap(a, lo + root, lo + child);
root = child;
}
}
static void intro(int[] a, int lo, int hi, int depth) {
while (hi - lo >= 16) {
if (depth == 0) { heapSort(a, lo, hi); return; } // fallback
depth--;
int mid = (lo + hi) >>> 1;
int p = medianOf3(a[lo], a[mid], a[hi]);
int i = lo, j = hi;
while (i <= j) {
while (a[i] < p) i++;
while (a[j] > p) j--;
if (i <= j) { swap(a, i, j); i++; j--; }
}
if (j - lo < hi - i) { intro(a, lo, j, depth); lo = i; }
else { intro(a, i, hi, depth); hi = j; }
}
insertionSort(a, lo, hi);
}
static void introSort(int[] a) {
if (a.length > 1) intro(a, 0, a.length - 1, 2 * (31 - Integer.numberOfLeadingZeros(a.length)));
}
static int medianOf3(int x, int y, int z) {
return Math.max(Math.min(x, y), Math.min(Math.max(x, y), z));
}
static void radixSort(int[] a) {
int[] src = a.clone(), dst = new int[a.length];
for (int shift = 0; shift < 32; shift += 8) {
int[] count = new int[257];
for (int x : src) count[(((x ^ 0x80000000) >>> shift) & 0xFF) + 1]++;
for (int b = 0; b < 256; b++) count[b + 1] += count[b];
for (int x : src) dst[count[((x ^ 0x80000000) >>> shift) & 0xFF]++] = x;
int[] t = src; src = dst; dst = t;
}
System.arraycopy(src, 0, a, 0, a.length);
}
static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
static final Map<String, Consumer<int[]>> SORTS = new LinkedHashMap<>();
static {
SORTS.put("insertion", SortLib::insertionSort);
SORTS.put("merge", SortLib::mergeSort);
SORTS.put("introsort", SortLib::introSort);
SORTS.put("heap", SortLib::heapSort);
SORTS.put("radix", SortLib::radixSort);
}
// ---------- acceptance tests ----------
static int[] range(int from, int to, int step) {
int n = Math.max(0, (to - from + step + (step > 0 ? -1 : 1)) / step);
int[] r = new int[n];
for (int i = 0; i < n; i++) r[i] = from + i * step;
return r;
}
static int[][] fixedCases() {
int[] fives = new int[50]; Arrays.fill(fives, 5);
int[] mod3 = new int[500]; for (int i = 0; i < 500; i++) mod3[i] = i % 3;
return new int[][]{{}, {1}, {2, 1}, {3, -1, 2, -1, 0}, fives,
{Integer.MAX_VALUE, Integer.MIN_VALUE, 0, -1, 1},
range(0, 999, 1), range(1000, 1, -1), mod3};
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
static void runTests() {
Random rng = new Random(42);
java.util.List<int[]> cases = new java.util.ArrayList<>(Arrays.asList(fixedCases()));
for (int t = 0; t < 300; t++) {
int[] r = new int[rng.nextInt(201)];
for (int i = 0; i < r.length; i++) r[i] = rng.nextInt(2001) - 1000;
cases.add(r);
}
for (var e : SORTS.entrySet()) {
for (int[] arr : cases) {
int[] b = arr.clone(), want = arr.clone();
e.getValue().accept(b);
Arrays.sort(want);
check(Arrays.equals(b, want), e.getKey() + " failed");
}
}
for (int[] arr : cases) { // test 11: the fallback path
int[] b = arr.clone(), want = arr.clone();
if (b.length > 0) intro(b, 0, b.length - 1, 0);
Arrays.sort(want);
check(Arrays.equals(b, want), "intro depth 0 failed");
}
System.out.println("all acceptance tests passed");
}
// ---------- benchmark (printed, never asserted) ----------
static final int BENCH_N = 2000;
static int[] make(String shape, int n, Random rng) {
int[] r = new int[n];
for (int i = 0; i < n; i++) {
switch (shape) {
case "random" -> r[i] = rng.nextInt();
case "sorted" -> r[i] = i;
case "reversed" -> r[i] = n - i;
default -> r[i] = rng.nextInt(10);
}
}
return r;
}
static void bench(int n, int reps) {
Random rng = new Random(1);
String[] shapes = {"random", "sorted", "reversed", "few-unique"};
Map<String, Consumer<int[]>> algos = new LinkedHashMap<>(SORTS);
algos.put("builtin", Arrays::sort);
int[][] data = new int[shapes.length][];
for (int s = 0; s < shapes.length; s++) data[s] = make(shapes[s], n, rng);
System.out.printf("n = %d, best of %d, milliseconds%n%12s", n, reps, "");
for (String s : shapes) System.out.printf("%12s", s);
System.out.println();
for (var e : algos.entrySet()) {
System.out.printf("%-12s", e.getKey());
for (int s = 0; s < shapes.length; s++) {
int[] want = data[s].clone(); Arrays.sort(want);
double best = Double.MAX_VALUE;
for (int r = 0; r < reps + 2; r++) { // first runs warm up the JIT
int[] b = data[s].clone();
long t0 = System.nanoTime();
e.getValue().accept(b);
long t1 = System.nanoTime();
check(Arrays.equals(b, want), "bench output wrong");
if (r >= 2) best = Math.min(best, (t1 - t0) / 1e6);
}
System.out.printf("%12.3f", best);
}
System.out.println();
}
}
public static void main(String[] args) {
runTests();
bench(BENCH_N, 3);
}
}
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <functional>
#include <limits>
#include <random>
#include <string>
#include <utility>
#include <vector>
using Vec = std::vector<int>;
// ---------- the five sorts: each sorts std::vector<int> in place ----------
void insertionSort(Vec& a, int lo, int hi) {
for (int i = lo + 1; i <= hi; ++i) {
int x = a[i], j = i - 1;
while (j >= lo && a[j] > x) { a[j + 1] = a[j]; --j; }
a[j + 1] = x;
}
}
void mergeRec(Vec& a, Vec& buf, int lo, int hi) {
if (hi - lo < 16) { insertionSort(a, lo, hi); return; }
int mid = lo + (hi - lo) / 2;
mergeRec(a, buf, lo, mid);
mergeRec(a, buf, mid + 1, hi);
if (a[mid] <= a[mid + 1]) return; // halves already in order
std::copy(a.begin() + lo, a.begin() + hi + 1, buf.begin() + lo);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; ++k) {
if (i > mid) a[k] = buf[j++];
else if (j > hi) a[k] = buf[i++];
else if (buf[j] < buf[i]) a[k] = buf[j++]; // ties take the left (stable)
else a[k] = buf[i++];
}
}
void mergeSort(Vec& a) {
Vec buf(a.size()); // one auxiliary buffer
mergeRec(a, buf, 0, static_cast<int>(a.size()) - 1);
}
void sift(Vec& a, int lo, int root, int size) {
while (true) {
int child = 2 * root + 1;
if (child >= size) return;
if (child + 1 < size && a[lo + child + 1] > a[lo + child]) ++child;
if (a[lo + root] >= a[lo + child]) return;
std::swap(a[lo + root], a[lo + child]);
root = child;
}
}
void heapSortRange(Vec& a, int lo, int hi) {
int n = hi - lo + 1;
for (int r = n / 2 - 1; r >= 0; --r) sift(a, lo, r, n);
for (int end = n - 1; end > 0; --end) {
std::swap(a[lo], a[lo + end]);
sift(a, lo, 0, end);
}
}
void intro(Vec& a, int lo, int hi, int depth) {
while (hi - lo >= 16) {
if (depth == 0) { heapSortRange(a, lo, hi); return; } // fallback
--depth;
int mid = lo + (hi - lo) / 2;
int x = a[lo], y = a[mid], z = a[hi];
int p = std::max(std::min(x, y), std::min(std::max(x, y), z)); // median of three
int i = lo, j = hi;
while (i <= j) {
while (a[i] < p) ++i;
while (a[j] > p) --j;
if (i <= j) { std::swap(a[i], a[j]); ++i; --j; }
}
if (j - lo < hi - i) { intro(a, lo, j, depth); lo = i; }
else { intro(a, i, hi, depth); hi = j; }
}
insertionSort(a, lo, hi);
}
int floorLog2(std::size_t n) { int r = 0; while (n >>= 1) ++r; return r; }
void introSort(Vec& a) {
if (a.size() > 1) intro(a, 0, static_cast<int>(a.size()) - 1, 2 * floorLog2(a.size()));
}
void radixSort(Vec& a) {
Vec src = a, dst(a.size());
for (int shift = 0; shift < 32; shift += 8) {
std::size_t count[257] = {};
for (int x : src) ++count[(((static_cast<std::uint32_t>(x) ^ 0x80000000u) >> shift) & 0xFFu) + 1];
for (int b = 0; b < 256; ++b) count[b + 1] += count[b];
for (int x : src) dst[count[((static_cast<std::uint32_t>(x) ^ 0x80000000u) >> shift) & 0xFFu]++] = x;
std::swap(src, dst);
}
a = src;
}
const std::vector<std::pair<std::string, std::function<void(Vec&)>>> SORTS = {
{"insertion", [](Vec& a) { insertionSort(a, 0, static_cast<int>(a.size()) - 1); }},
{"merge", mergeSort},
{"introsort", introSort},
{"heap", [](Vec& a) { heapSortRange(a, 0, static_cast<int>(a.size()) - 1); }},
{"radix", radixSort},
};
// ---------- acceptance tests ----------
std::vector<Vec> fixedCases() {
Vec up(1000), down(1000), mod3(500);
for (int i = 0; i < 1000; ++i) { up[i] = i; down[i] = 1000 - i; }
for (int i = 0; i < 500; ++i) mod3[i] = i % 3;
return {{}, {1}, {2, 1}, {3, -1, 2, -1, 0}, Vec(50, 5),
{std::numeric_limits<int>::max(), std::numeric_limits<int>::min(), 0, -1, 1},
up, down, mod3};
}
void runTests() {
std::mt19937 rng(42);
std::vector<Vec> cases = fixedCases();
for (int t = 0; t < 300; ++t) {
Vec r(rng() % 201);
for (int& x : r) x = static_cast<int>(rng() % 2001) - 1000;
cases.push_back(r);
}
for (const auto& [name, sort] : SORTS) {
for (const Vec& arr : cases) {
Vec b = arr, want = arr;
sort(b);
std::sort(want.begin(), want.end());
assert(b == want);
}
}
for (const Vec& arr : cases) { // test 11: the fallback path
Vec b = arr, want = arr;
if (!b.empty()) intro(b, 0, static_cast<int>(b.size()) - 1, 0);
std::sort(want.begin(), want.end());
assert(b == want);
}
std::puts("all acceptance tests passed");
}
// ---------- benchmark (printed, never asserted) ----------
constexpr int BENCH_N = 2000;
Vec make(const std::string& shape, int n, std::mt19937& rng) {
Vec r(n);
for (int i = 0; i < n; ++i) {
if (shape == "random") r[i] = static_cast<int>(rng());
else if (shape == "sorted") r[i] = i;
else if (shape == "reversed") r[i] = n - i;
else r[i] = static_cast<int>(rng() % 10);
}
return r;
}
void bench(int n, int reps) {
std::mt19937 rng(1);
const std::vector<std::string> shapes = {"random", "sorted", "reversed", "few-unique"};
std::vector<Vec> data;
for (const auto& s : shapes) data.push_back(make(s, n, rng));
auto algos = SORTS;
algos.push_back({"builtin", [](Vec& a) { std::sort(a.begin(), a.end()); }});
std::printf("n = %d, best of %d, milliseconds\n%12s", n, reps, "");
for (const auto& s : shapes) std::printf("%12s", s.c_str());
std::printf("\n");
for (const auto& [name, sort] : algos) {
std::printf("%-12s", name.c_str());
for (std::size_t s = 0; s < shapes.size(); ++s) {
Vec want = data[s];
std::sort(want.begin(), want.end());
double best = 1e300;
for (int r = 0; r < reps; ++r) {
Vec b = data[s];
auto t0 = std::chrono::steady_clock::now();
sort(b);
auto t1 = std::chrono::steady_clock::now();
assert(b == want);
best = std::min(best, std::chrono::duration<double, std::milli>(t1 - t0).count());
}
std::printf("%12.3f", best);
}
std::printf("\n");
}
}
int main() {
runTests();
bench(BENCH_N, 3);
}
import assert from "node:assert/strict";
type SortFn = (a: number[]) => void;
// ---------- the five sorts: each sorts number[] (int32 values) in place ----------
function insertionSort(a: number[], lo = 0, hi = a.length - 1): void {
for (let i = lo + 1; i <= hi; i++) {
const x = a[i];
let j = i - 1;
while (j >= lo && a[j] > x) { a[j + 1] = a[j]; j--; }
a[j + 1] = x;
}
}
function mergeSort(a: number[]): void {
const buf = a.slice(); // one auxiliary buffer
const rec = (lo: number, hi: number): void => {
if (hi - lo < 16) { insertionSort(a, lo, hi); return; }
const mid = (lo + hi) >> 1;
rec(lo, mid);
rec(mid + 1, hi);
if (a[mid] <= a[mid + 1]) return; // halves already in order
for (let k = lo; k <= hi; k++) buf[k] = a[k];
let i = lo, j = mid + 1;
for (let k = lo; k <= hi; k++) {
if (i > mid) a[k] = buf[j++];
else if (j > hi) a[k] = buf[i++];
else if (buf[j] < buf[i]) a[k] = buf[j++]; // ties take the left (stable)
else a[k] = buf[i++];
}
};
rec(0, a.length - 1);
}
function heapSort(a: number[], lo = 0, hi = a.length - 1): void {
const n = hi - lo + 1;
const sift = (root: number, size: number): void => {
while (true) {
let child = 2 * root + 1;
if (child >= size) return;
if (child + 1 < size && a[lo + child + 1] > a[lo + child]) child++;
if (a[lo + root] >= a[lo + child]) return;
[a[lo + root], a[lo + child]] = [a[lo + child], a[lo + root]];
root = child;
}
};
for (let r = (n >> 1) - 1; r >= 0; r--) sift(r, n);
for (let end = n - 1; end > 0; end--) {
[a[lo], a[lo + end]] = [a[lo + end], a[lo]];
sift(0, end);
}
}
function intro(a: number[], lo: number, hi: number, depth: number): void {
while (hi - lo >= 16) {
if (depth === 0) { heapSort(a, lo, hi); return; } // fallback
depth--;
const mid = (lo + hi) >> 1;
const x = a[lo], y = a[mid], z = a[hi];
const p = Math.max(Math.min(x, y), Math.min(Math.max(x, y), z)); // median of three
let i = lo, j = hi;
while (i <= j) {
while (a[i] < p) i++;
while (a[j] > p) j--;
if (i <= j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; }
}
if (j - lo < hi - i) { intro(a, lo, j, depth); lo = i; }
else { intro(a, i, hi, depth); hi = j; }
}
insertionSort(a, lo, hi);
}
function introSort(a: number[]): void {
if (a.length > 1) intro(a, 0, a.length - 1, 2 * Math.floor(Math.log2(a.length)));
}
function radixSort(a: number[]): void {
let src = a.slice();
let dst = new Array<number>(a.length);
for (let shift = 0; shift < 32; shift += 8) {
const count = new Array<number>(257).fill(0);
for (const x of src) count[(((x ^ 0x80000000) >>> shift) & 0xff) + 1]++;
for (let b = 0; b < 256; b++) count[b + 1] += count[b];
for (const x of src) dst[count[((x ^ 0x80000000) >>> shift) & 0xff]++] = x;
[src, dst] = [dst, src];
}
for (let i = 0; i < a.length; i++) a[i] = src[i];
}
const SORTS: Record<string, SortFn> = {
insertion: (a) => insertionSort(a),
merge: mergeSort,
introsort: introSort,
heap: (a) => heapSort(a),
radix: radixSort,
};
// ---------- acceptance tests ----------
const builtin = (a: number[]): number[] => a.slice().sort((x, y) => x - y);
function fixedCases(): number[][] {
return [[], [1], [2, 1], [3, -1, 2, -1, 0], new Array<number>(50).fill(5),
[2147483647, -2147483648, 0, -1, 1],
Array.from({ length: 1000 }, (_, i) => i),
Array.from({ length: 1000 }, (_, i) => 1000 - i),
Array.from({ length: 500 }, (_, i) => i % 3)];
}
function runTests(): void {
const cases = fixedCases();
for (let t = 0; t < 300; t++) {
const len = Math.floor(Math.random() * 201);
cases.push(Array.from({ length: len }, () => Math.floor(Math.random() * 2001) - 1000));
}
for (const [name, sort] of Object.entries(SORTS)) {
for (const arr of cases) {
const b = arr.slice();
sort(b);
assert.deepEqual(b, builtin(arr), name);
}
}
for (const arr of cases) { // test 11: the fallback path
const b = arr.slice();
if (b.length > 0) intro(b, 0, b.length - 1, 0);
assert.deepEqual(b, builtin(arr), "intro depth 0");
}
console.log("all acceptance tests passed");
}
// ---------- benchmark (printed, never asserted) ----------
const BENCH_N = 2000;
function make(shape: string, n: number): number[] {
return Array.from({ length: n }, (_, i) =>
shape === "random" ? (Math.random() * 2 ** 32) | 0
: shape === "sorted" ? i
: shape === "reversed" ? n - i
: Math.floor(Math.random() * 10));
}
function bench(n: number, reps: number): void {
const shapes = ["random", "sorted", "reversed", "few-unique"];
const data = shapes.map((s) => make(s, n));
const algos: Record<string, SortFn> = { ...SORTS, builtin: (a) => { a.sort((x, y) => x - y); } };
console.log(`n = ${n}, best of ${reps}, milliseconds`);
console.log("".padEnd(12) + shapes.map((s) => s.padStart(12)).join(""));
for (const [name, sort] of Object.entries(algos)) {
let row = name.padEnd(12);
data.forEach((d) => {
const want = builtin(d);
let best = Infinity;
for (let r = 0; r < reps + 2; r++) { // first runs warm up the JIT
const b = d.slice();
const t0 = performance.now();
sort(b);
const t1 = performance.now();
assert.deepEqual(b, want);
if (r >= 2) best = Math.min(best, t1 - t0);
}
row += best.toFixed(3).padStart(12);
});
console.log(row);
}
}
runTests();
bench(BENCH_N, 3);
Things worth noticing in the reference code:
- Median of three without branches on the hot path.
max(min(x, y), min(max(x, y), z))is the median of three values; it needs no temporary array and cannot overflow. - The partition never runs off the array. The pivot value is one of
a[lo],a[mid],a[hi], so on the first scan each pointer stops at or before the element holding it; after every swap, the swapped elements act as sentinels for the next scan. - Radix keys flip the sign bit.
(x ^ 0x80000000) >>> shiftin Java and TypeScript, an unsigned cast in C++,x + 2**31in Python. Test 6 catches the version that forgets.
What the numbers should look like
Two runs of the reference code on our machine (Windows 11), best of 3, in milliseconds. Your absolute numbers will differ; the shape should not.
Python (CPython 3.14), — the reference program exactly as printed above:
| Algorithm | Random | Sorted | Reversed | Few unique |
|---|---|---|---|---|
| insertion | 73.95 | 0.26 | 139.69 | 59.62 |
| merge | 2.51 | 0.21 | 2.46 | 2.15 |
| introsort | 1.71 | 0.68 | 0.72 | 1.17 |
| heap | 5.91 | 5.66 | 5.08 | 4.83 |
| radix | 2.12 | 1.87 | 1.88 | 1.85 |
| built-in (Timsort) | 0.31 | 0.01 | 0.01 | 0.13 |
C++ (MSVC, /O2), — BENCH_N = 1000000, insertion sort removed from the registry:
| Algorithm | Random | Sorted | Reversed | Few unique |
|---|---|---|---|---|
| merge | 109.9 | 2.3 | 20.1 | 42.0 |
| introsort | 83.6 | 8.5 | 8.4 | 25.8 |
| heap | 100.0 | 52.8 | 52.2 | 55.2 |
| radix | 10.5 | 22.4 | 22.5 | 15.7 |
std::sort | 91.3 | 7.4 | 9.4 | 13.9 |
What to notice, and what to explain in your write-up:
- Insertion sort spans three orders of magnitude. It is among the fastest on sorted input (one comparison per element) and the slowest by far on reversed input (about million element shifts). Random input costs about half of reversed, because a random permutation has inversions on average. This is the bound made visible.
- Merge sort is adaptive only because of one line. The
a[mid] <= a[mid + 1]check turns sorted input into a linear pass. In C++, reversed input is also 5× faster than random although it does just as many merges: every comparison in a merge goes the same way, so the CPU's branch predictor is never wrong. In Python the interpreter overhead hides that effect. - Introsort is your fastest comparison sort on random input in both languages, and never triggers its fallback here; sorted and reversed inputs are its best cases because median-of-three picks the exact median. If you replace median-of-three with "first element", sorted input becomes quadratic without the fallback and heap sort with it — measure both to see the safety net work.
- Heap sort is the slowest sort and the least adaptive. It does about comparisons and gains nothing from sorted input (52 ms versus introsort's 8 ms in C++). On random input at it was only 1.2× slower than introsort, but sift-down jumps from index to , so once the array is far larger than the CPU caches most steps miss; try and and watch the gap grow (How Data Structures Live in Memory).
- Radix sort barely notices the input shape. Four passes no matter what. In C++ at it beat
std::sorton random input by almost 9× (10.5 ms versus 91 ms). In Python it loses to introsort at but wins at (110 ms versus 121 ms in our run), because its cost per element is constant while the comparison sorts pay . - The built-in sort wins by 5–70× in Python because it is written in C, not because Timsort is asymptotically better. In C++ your introsort lands close to
std::sort(84 ms versus 91 ms on random). Python's Timsort (with the Powersort merge policy since 3.11) is also adaptive: it detects the single ascending run in sorted input and the single descending run in reversed input (which it reverses in place), finishing both in linear time.
Stretch goals
- Comparators and stability. Generalise the interface to
sort(a, key)over records. Write a test that sorts(key, original_index)pairs with many equal keys and checks that merge and insertion sort preserve the original order while introsort and heap sort do not. - Count comparisons. Wrap elements in an object whose comparison increments a counter. Plot comparisons divided by for each algorithm as grows: merge sort tends to about 1, heap sort to about 2, introsort to about 1.1–1.2 with median-of-three.
- Natural runs. Add a run-detecting merge sort that finds maximal ascending (and strictly descending, reversed) runs and merges them pairwise — a mini Timsort. Benchmark it on "sorted with 1% random swaps" and "sawtooth" inputs.
- Pattern-defeating quicksort. Read Orson Peters' pdqsort paper (arXiv:2106.05123) and add its tricks one at a time: block partitioning to avoid branch mispredictions, detection of already-partitioned ranges, and shuffling a few elements after a bad partition. Measure each trick separately.
- Adversarial input. Implement McIlroy's "A Killer Adversary for Quicksort" (Software: Practice and Experience, 1999), which constructs inputs on the fly that drive any quicksort to quadratic time. Run it against your introsort with and without the depth budget.
- Radix for other types. Sort 64-bit integers (8 passes, or 4 passes of 16 bits), IEEE floats (flip all bits of negatives, only the sign bit of positives), and strings with MSD radix sort.
Further reading
- D. R. Musser, "Introspective Sorting and Selection Algorithms", Software: Practice and Experience 27(8), 1997.
- R. Sedgewick and K. Wayne, Algorithms, 4th ed., Chapter 2 (elementary sorts, mergesort, quicksort, priority queues) and §5.1 (string sorts, LSD and MSD radix).
- CLRS, Introduction to Algorithms, Chapters 2, 6, 7 and 8 (insertion and merge sort, heapsort, quicksort, linear-time sorting).
- O. Peters, "Pattern-defeating Quicksort", arXiv:2106.05123, 2021.
- T. Peters,
listsort.txtin the CPython source tree — the design notes for Timsort. - Archon: Sorting & Searching (overview), Sorting in the Real World, Quickselect & Order Statistics, Benchmarks, Testing & Debugging Algorithms.
Module 2 navigation. Previous: Quickselect, Median of Medians & Order Statistics. Next module: Module 3 · Trees. Module overview: Searching & Sorting. Course home: DSA: Zero to Mastery.