Sorting Algorithms
Every frame your engine sorts something: draw calls by shader and depth, transparent sprites back to front, particles, physics bounding boxes. Pick the wrong sort, or the wrong key, and a job that should take a tenth of a millisecond takes several. This page shows you how to choose: what the library sorts actually do (introsort, pdqsort, timsort and their parts), when a radix sort on a packed integer key beats them all, and how to build that key. The core routines are written from scratch in C++, every one runs live in the browser, and the page ends with case studies from shipping engines.
- Estimate what a sort costs per frame from its comparison count and the cost of one comparison, and spot when the comparator, not the algorithm, is the problem.
- Pick the right sort for a job:
std::sort, a stable sort, timsort for nearly sorted data, radix or counting sort for integer keys, a GPU sort for GPU data. - Pack draw calls into a 64-bit sort key that orders opaque draws front to back and transparent ones back to front, including float depth.
- Explain how introsort and pdqsort guard against quicksort's quadratic worst case, and why every library sort switches to insertion sort for small ranges.
- Avoid the comparator bugs that crash or corrupt
std::sort: NaN keys, inconsistent ordering, overflow ina - b.
01Why a sort, not a stopwatch
A large scene can submit thousands to tens of thousands of draw calls per frame, and the renderer wants them grouped by render target, then shader, then material, then depth, so the GPU changes state as rarely as possible[1]. Sorting them with std::sort and a comparator that looks up each draw's material can eat over a millisecond of a 16.67 ms frame. Sorting the same draws by a packed integer key with a radix sort takes about a tenth of a millisecond.
Here's where the time goes. At 5,000 to 15,000 draws, a comparison sort does roughly 1.2 to 1.4 n log₂ n key comparisons, about 70,000 to 290,000. If the comparator dereferences a material or shader pointer, each comparison can cost tens of nanoseconds once the pointer chasing leaves the L1 cache, and the total runs past a millisecond. A four-pass radix sort over a packed 32-bit key does the same job in roughly 0.1 ms. Bevy measured this swap in 2022: on its many_cubes benchmark the median time of the opaque-3D sort phase dropped from 0.728 ms to 0.094 ms, though the same patch slowed two sprite benchmarks (§16)[2]. At this scale log₂ n is only about 12 to 14, so most of the gap comes from the key and the memory layout, not from the log factor.
Worked example
5,000 draws. log₂ 5,000 ≈ 12.3, so a comparison sort does about 1.2 × 5,000 × 12.3 ≈ 74,000 comparisons.
At 30 ns each (a pointer dereference that misses the cache, plus a short compare): 74,000 × 30 ns ≈ 2.2 ms.
A radix sort makes 4 passes over a packed 32-bit key at roughly 3 ns per element per pass: 4 × 3 ns × 5,000 = 0.06 ms, more than 30 times less.
This page walks through the family of sorts an engine programmer actually meets. Comparison sorts (quicksort, mergesort, heapsort, and their modern hybrids) are bounded below by Ω(n log n) for n distinct elements, a bound proved in §3. Non-comparison sorts (radix, counting, bucket) escape that bound by looking at the bits of the keys directly, which is why many renderers reach for them. Parallel sorts (bitonic, GPU radix) spread the work across thousands of GPU threads; bitonic sort even accepts more total work, O(n log² n), in exchange for a fixed, data-independent schedule.
The cost of the wrong sort
Whether that gap matters depends on how many items you sort and what one comparison costs. The widget below puts a comparison sort and a radix sort on the same axis: object count along the X, milliseconds per frame along the Y. The comparison curve is n log₂ n comparisons at an assumed ~30 ns each (a pointer dereference that misses cache plus a short string compare, ballparked from Norvig's latency numbers[3]). The radix curve is linear in n at ~3 ns per element per pass, four passes for a 32-bit key, plus roughly 2 µs of fixed setup (clearing and prefix-summing four 256-entry histograms). The crossover sits where that setup cost stops dominating: around n ≈ 100 with a 5 ns comparator, under twenty items with the 30 ns comparator (§12). With the 30 ns comparator, above 1,000 items the gap is an order of magnitude or more:
02A short history of sorting
Machine sorting predates electronic computers by half a century. Herman Hollerith's punched-card equipment tabulated the 1890 US Census, and the electromechanical card sorters that followed it ordered a deck one column at a time, least significant digit first: LSD radix sort[4]. You don't need the rest of the history to pick a sort, but two patterns from it explain what the library sorts look like today.
First, the major standard-library sorts are hybrids: quicksort plus insertion sort plus a heapsort fallback (introsort, pdqsort), or mergesort plus insertion sort on short runs plus galloping merges (timsort, powersort). Second, the famous bugs were in the bookkeeping around the comparison loop, not the loop itself: the 2015 timsort stack-invariant bug was in the merge-stack logic, and the binary-search overflow Joshua Bloch reported in 2006[17] was in the midpoint arithmetic.
Timeline: von Neumann's merge sort to Rust's ipnsort
qsort and a generation of C library sorts descend from this paper.
std::sort has been introsort since the GCC 3.x era, inherited from the SGI STL; MSVC's STL also uses it, and libc++ added the depth limit in LLVM 14[22].
list.sort. The design document Objects/listsort.txt is a model of how to write up a sort. Joshua Bloch's port landed in OpenJDK in 2009 (JDK-6804124) and shipped with Java 7 in 2011 as the default sort for object arrays. V8 adopted timsort for JavaScript Array.prototype.sort in V8 v7.0 (2018).
ArrayIndexOutOfBoundsException on a constructed sequence of runs; CPython's run stack was large enough that no input that fits in memory could overflow it. CPython fixed the merge logic and OpenJDK enlarged the stack. A sort in production for thirteen years could overrun its run stack.
slice::sort_unstable in 2017, and Boost shipped a port. It stayed Rust's unstable sort until Rust 1.81 (2024) replaced it with the ipnsort-based implementation[32].
03Why comparison sorts can't beat n log n
You've tuned a comparison sort's pivot and cutoffs, and it still costs too much. Is there a cleverer comparison sort out there? Not one that needs asymptotically fewer comparisons, and knowing that tells you when to stop tuning and change the approach. Any algorithm that sorts by comparing pairs of elements (no peeking at their bits, no precomputed table) must do about n log2 n comparisons in the worst case. The proof is a short counting argument, and it also explains how radix sort and counting sort get under the bound: they break its one assumption.
Model a comparison sort as a decision tree: the root is the first comparison the algorithm makes; the two children are the two possible outcomes; each leaf is one possible final permutation. For an input of n distinct elements there are n! possible permutations, so the tree needs at least n! leaves. A binary tree with L leaves has height at least log2 L. So the height (the worst-case number of comparisons on some input) is at least log2(n!).
Worked example
n = 3: there are 3! = 6 orderings. Each comparison has two outcomes, so 2 comparisons can tell apart at most 4 orderings and 3 can tell apart 8. At least 3 comparisons are needed.
n = 10: 10! = 3,628,800 orderings, and log2 3,628,800 ≈ 21.8, so at least 22.
n = 5,000: log2(5,000!) ≈ 54,200 comparisons at the very least. The 74,000 in §1 is within 40% of that floor, so no comparison sort will do this job several times faster.
The equation turns "log2(n!)" into something you can compare with n log n. It uses a Stirling-type bound, n! > (n/e)n for n ≥ 1[18]:
In words: every comparison sort needs at least about n log2 n − 1.443 n comparisons on some input. The 1.443 n part grows more slowly than n log n, so for large n the floor is essentially n log n. Mergesort and heapsort match this bound up to a constant factor in the worst case; quicksort matches it on average.
The widget below builds the decision tree for n = 3 by hand. There are 3! = 6 permutations, so the tree has 6 leaves and minimum height ⌈log2(6)⌉ = 3 comparisons. Click a permutation to highlight the path:
So how does radix sort beat the bound?
Radix sort never asks "is a less than b?". It looks at the bits of each key directly: bucket by the low byte, then the next byte, then the next. The decision-tree model does not apply because the algorithm is not making binary decisions on comparison outcomes; it is doing a constant amount of work per byte per element.
For an n-element array of w-bit keys, radix sort runs in O((w / b) · (n + 2b)) where b is the bits per pass: w / b passes, each touching every element plus a 2b-entry histogram. With w = 32, b = 8, that is four linear passes. Asymptotically it is O(n) when w is fixed (which it is for draw-call keys). The bound in §3 only forbids beating n log n with comparisons.
04Insertion sort, the small-n champion
A quicksort that recurses all the way down to one-element ranges spends most of its calls on tiny subarrays, where picking a pivot and recursing cost more than the sorting. Every library sort stops recursing at some small size and finishes with insertion sort instead. Insertion sort is what most production sorts fall back to at small sizes. Its worst case is O(n²), which is easy to file under "bad" and move on, but that misses the small-n regime: insertion sort usually wins below roughly 16 to 32 elements on current CPUs, which is exactly the size of the subarrays a recursive sort produces at the bottom of its recursion. The reasons are mechanical, not asymptotic: a tight inner loop, no recursion or pivot selection, and sequential memory access that stays in L1.
template<typename It, typename Compare> void insertion_sort(It first, It last, Compare less) { if (first == last) return; // first + 1 would step past an empty range. // Outer loop: bring *cursor into its place among the sorted prefix [first, cursor). for (It cursor = first + 1; cursor != last; ++cursor) { auto key = std::move(*cursor); // Save the element we're placing. It target = cursor; // Walk left while the element on the left is bigger than key. while (target != first && less(key, *(target - 1))) { *target = std::move(*(target - 1)); // Shift the bigger one right by one slot. --target; } *target = std::move(key); // Drop key into the gap. } }
Cost analysis: the outer loop runs n − 1 times; the inner loop walks back as far as the new element needs to go. On a fully sorted input the inner loop exits immediately and the total cost is O(n). On a reverse-sorted input the inner loop walks all the way back every time and the total cost is n(n−1)/2 = Θ(n²). The average case on random data is also Θ(n²), about n²/4 shifts: on average half of the elements to the left of each new element are larger than it, so the average is half the worst case.
Worked example
16 elements. Already sorted: each of the 15 new elements is compared once and stays put, so 15 comparisons and no shifts.
Reverse sorted: the i-th new element shifts past all i before it, so 1 + 2 + … + 15 = 120 shifts.
Random: about half of that, 16² / 4 = 64 shifts on average. At this size those 64 shifts move data that's already in L1.
The widget below races insertion sort against a simple recursive quicksort (median-of-three pivot, Lomuto partition) at array sizes from 4 to 256. The crossover is what production cutoffs are tuned to:
Why don't all sorts cut over at the same n?
The crossover depends on what a comparison and a move cost. For primitive types (ints, floats) both are a single instruction, so insertion sort's extra work is cheap and the cutoff can sit high (Java's DualPivotQuicksort uses 44 for primitive arrays). When elements are expensive to move, the cutoff drops: libc++ in LLVM 14 to 16 used 30 for trivially copyable types but only 6 for everything else, because each shift of a non-trivial type is a real move-assignment call. When comparisons are expensive, sorts reach for binary insertion sort, which finds each element's slot in log2 k comparisons and pays only in moves: Java's object sort (timsort) extends short runs to 16 to 32 elements that way.
Cache behavior barely separates the two at these sizes, since a subarray of a few dozen elements sits in L1 either way. The difference is instruction overhead: pivot selection, the partition loop's bookkeeping, and the recursive calls cost more than a few shifts.
05Quicksort: partition, recurse, pray
A sort that handles a million random keys in milliseconds can take far longer on the same keys already in order, if it picks its pivots badly. Quicksort is the fast algorithm with that hazard built in. Tony Hoare's quicksort, from his 1959 stint at Moscow State University, is the basis of most general-purpose unstable sorts in standard libraries (introsort, pdqsort, dual-pivot quicksort). Pick a pivot, partition the array into "less than pivot" and "greater than pivot," and recurse on each side. The expected cost is n log n and the worst case is n²; which one you get depends on how the pivot is chosen.
The partition
Two partition schemes ship in production code. Hoare's partition does fewer swaps; Lomuto's partition is simpler to write correctly. The C++ standard libraries use tuned variants of Hoare's; branchless Lomuto variants have come back in newer sorts such as Rust's current sort_unstable. A Hoare partition in C++:
// Partitions [first, last) around the value of *first and returns a cut: // every element of [first, cut) is <= pivot, every element of [cut, last) // is >= pivot, and neither side is empty. Requires last - first >= 2. template<typename It, typename Compare> It hoare_partition(It first, It last, Compare less) { auto pivot = *first; // Copy it: the swaps below move the original. Production code // first swaps a median-of-3 (or ninther) into *first. It leftCursor = first; It rightCursor = last - 1; while (true) { while (less(*leftCursor, pivot)) ++leftCursor; // Stop on something >= pivot. while (less(pivot, *rightCursor)) --rightCursor; // Stop on something <= pivot. if (leftCursor >= rightCursor) return rightCursor + 1; // Cursors met or crossed; done. std::iter_swap(leftCursor, rightCursor); // Swap the out-of-place pair... ++leftCursor; // ...and step past it. The swapped --rightCursor; // values stop the next scans in bounds. } }
The recursion is the easy part; quicksort variants differ mostly in how they pick the pivot.
The pivot problem
Worked example
Sort 48 already-sorted keys with the first element as pivot (the widget below). Each pivot is the smallest key left, so each partition peels off one element: 47 + 46 + … + 1 = 1,128 comparisons and a recursion 47 deep.
Median-of-three on the same input picks the true middle every time: 183 comparisons and depth 5.
If the pivot is the median of the data, quicksort halves the array each call and runs in n log n. If the pivot is the minimum (or maximum) every time, one side is empty, the recursion depth approaches n, and the cost is quadratic; for large n the call stack can overflow too, unless the implementation recurses on the smaller side and loops on the larger.
Pivot strategies in roughly increasing sophistication:
- First element. Trivial. Worst case on already-sorted input, a common shape in real data. This is the textbook version; production libraries avoid it.
- Random element. Expected n log n on every input, and no fixed input can force quadratic behavior. Libraries mostly prefer median-of-three anyway: it splits more evenly on average and keeps the sort deterministic.
- Median-of-three. Sample the first, middle, and last element; use their median. Defeats sorted and reverse-sorted inputs. Bentley and McIlroy's 1993 sort uses it for mid-sized arrays (8 to 40 elements in their tuning)[8].
- Pseudomedian-of-nine ("ninther"). For large arrays, sample three groups of three, take the median of each, then the median of those medians. Bentley and McIlroy again, borrowing Tukey's ninther. Much harder to hit by accident.
- Median of medians (BFPRT). Compute the exact median in O(n). Guarantees n log n worst case, but the constant is large enough that it is rarely used for sorting.
Modern hybrids (introsort, pdqsort) give up on pivot perfection and accept that any deterministic strategy can be defeated. They monitor recursion depth or partition quality and take a fallback path when things go wrong: introsort switches to heapsort (§8); pdqsort first shuffles a few elements to break up patterns and falls back to heapsort if bad partitions keep coming (§10).
The widget below shows quicksort running on data you control. Switch the pivot strategy and the input shape to see when quicksort runs at n log n and when it falls apart:
06Mergesort, the stability champion
Two sprites sit at exactly the same depth. Sorted with an unstable sort, they can swap places from one frame to the next, and the overlap flickers. A stable sort keeps equal keys in their original order, and mergesort is the classic stable sort. It's von Neumann's algorithm. Split the array in half; recursively sort each half; merge the two sorted halves into one. The merge step is the substance of the algorithm: two cursors walking forward, copying the smaller of the two current elements into the output. The recursion is log2n levels deep; each level does O(n) work; total n log n, worst case and average case both.
Mergesort's selling points over quicksort:
- Stable. Elements with equal keys end up in their original relative order. This is required for the "sort by department, then sort by name" pattern, and for draw-call sorts where ties are broken by submission order.
- Worst case is n log n. No adversarial input. Quicksort needs pivot tricks; mergesort needs nothing.
- External-memory friendly. Merge is purely sequential reads and writes, no random access. Sorts on tape and disk were almost always merge-based in the mainframe era, and external sorts of very large inputs still are.
- Parallelizes cleanly. Each half can be sorted on its own core with no synchronization until the merge.
The drawbacks are the reason it is not the default in-memory sort. Mergesort needs O(n) auxiliary memory for the merge buffer; quicksort sorts in place with O(log n) stack. The merge also moves every element at every level (into the buffer and back), while a partition swaps only the elements on the wrong side. For in-memory arrays of primitives a tuned quicksort usually beats a tuned mergesort, and std::sort doesn't have to be stable, so the C++ libraries use introsort there and keep mergesort for std::stable_sort.
template<typename T> void merge(T* values, T* buffer, int lo, int mid, int hi) { // Copy [lo, hi) to the scratch buffer; merge from the buffer back into values. for (int k = lo; k < hi; ++k) buffer[k] = values[k]; int leftCursor = lo, rightCursor = mid; for (int writeAt = lo; writeAt < hi; ++writeAt) { if (leftCursor >= mid) values[writeAt] = buffer[rightCursor++]; else if (rightCursor >= hi) values[writeAt] = buffer[leftCursor++]; else if (buffer[rightCursor] < buffer[leftCursor]) values[writeAt] = buffer[rightCursor++]; else values[writeAt] = buffer[leftCursor++]; // Ties take the left: stable. } } template<typename T> void mergesort(T* values, T* buffer, int lo, int hi) { if (hi - lo < 2) return; // Production: cut over to insertion sort below ~16. int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 can overflow int on huge arrays; this can't. mergesort(values, buffer, lo, mid); mergesort(values, buffer, mid, hi); merge(values, buffer, lo, mid, hi); }
Worked example
Merge [2, 5, 9] with [3, 4, 10]. Compare the fronts: 2 < 3, take 2. 5 > 3, take 3. 5 > 4, take 4. 5 < 10, take 5. 9 < 10, take 9. The left side is empty, so copy 10.
Result [2, 3, 4, 5, 9, 10] after 5 comparisons for 6 elements. A merge of two runs never needs more comparisons than elements minus one.
The midpoint comment matters. In 2006 Joshua Bloch reported that the (lo + hi) / 2 in the Java standard library's binary search overflows once an array reaches 230 elements; the bug had sat in the JDK for nine years, and the binary search in Bentley's Programming Pearls (1986) had it too[17]. The fix, lo + (hi − lo) / 2, is the same one a mergesort midpoint needs.
Worked example
lo = 1,500,000,000 and hi = 1,600,000,000 both fit in a 32-bit int, whose maximum is 2,147,483,647. But lo + hi = 3,100,000,000 doesn't: it wraps to a negative number, and (lo + hi) / 2 is a negative index.
lo + (hi − lo) / 2 = 1,500,000,000 + 50,000,000 = 1,550,000,000, with no intermediate value above hi.
07Heapsort, the worst-case insurance policy
Some code can neither allocate a scratch buffer nor risk a quadratic blow-up: a kernel, an embedded C library, or quicksort's own emergency exit. It needs a sort that's in place and guaranteed n log n. Heapsort, J.W.J. Williams 1964[6], is the in-place worst-case-n log n sort. Quicksort can degrade to quadratic; mergesort needs n auxiliary words; heapsort needs neither. Production code mostly uses heapsort as a fallback: introsort calls it when recursion depth exceeds its budget. Code that can neither allocate a merge buffer nor risk quadratic time, such as some kernel and embedded C libraries, uses it directly.
The algorithm has two phases. First, build a max-heap in place: the largest element ends up at index 0. Then repeatedly swap the root (largest remaining) to the end of the array and sift down what landed at the root to restore the heap property. Each swap-pop step takes O(log n) sift-down time, done n times: O(n log n) total.
The non-obvious part is the build. The naive method (insert n elements one by one) is n log n. Floyd's bottom-up heapify, published the same year as Williams' paper[7], is O(n). The proof is a geometric sum: half the array is at the leaves and needs zero sift-down, a quarter is at level h−1 and needs at most one sift-down step, an eighth needs at most two, and the sum Σ k · 2−k is bounded by a constant.
Worked example
A full heap of 1,023 elements has 10 levels. The 512 leaves need no sift-down. The 256 nodes above them sink at most 1 level, the 128 above those at most 2, and so on up to the root, which sinks at most 9.
Total: 256 × 1 + 128 × 2 + 64 × 3 + 32 × 4 + 16 × 5 + 8 × 6 + 4 × 7 + 2 × 8 + 1 × 9 = 1,013 sift-down steps at most, fewer than one per element. Inserting the elements one by one could cost up to 9 steps each, about 9,000.
template<typename T> void sift_down(T* values, int root, int heapEnd) { // Walk root down toward the leaves; at each step, swap with the larger child if needed. while (true) { int leftChild = 2 * root + 1; int rightChild = 2 * root + 2; int biggest = root; if (leftChild < heapEnd && values[leftChild] > values[biggest]) biggest = leftChild; if (rightChild < heapEnd && values[rightChild] > values[biggest]) biggest = rightChild; if (biggest == root) return; // Heap property restored. std::swap(values[root], values[biggest]); root = biggest; // Follow the swap down. } } template<typename T> void heapsort(T* values, int count) { // Phase 1: build a max-heap in place, bottom-up. Floyd's O(n) heapify. for (int i = count / 2 - 1; i >= 0; --i) sift_down(values, i, count); // Phase 2: extract the max count - 1 times, growing a sorted suffix. for (int heapEnd = count - 1; heapEnd > 0; --heapEnd) { std::swap(values[0], values[heapEnd]); // Largest remaining moves to its final slot. sift_down(values, 0, heapEnd); // Restore the heap on the shrinking prefix. } }
The catch is speed. Heapsort is n log n in the worst case, but Musser reports it taking 2 to 5 times as long as quicksort on most inputs[9]. Two common causes: sift-down makes about two comparisons per level with unpredictable outcomes, and its parent-to-child jumps double in stride at every level, so once the heap outgrows a cache level those reads pay the next level's latency. Quicksort's partition streams through contiguous memory that the prefetcher handles well. Heapsort earns its place where the worst-case guarantee matters more than average speed.
08Introsort: quicksort with a parachute
A library sort can't know what input it'll get, and some inputs are built on purpose to defeat quicksort's pivot choice. David Musser's 1997 introsort[9] lets a library keep quicksort's speed and still promise O(n log n) in the worst case, which C++11 made a requirement for std::sort. Run quicksort, count recursion depth, and if it exceeds 2 log2n, finish the current subarray with heapsort. Quicksort's average case stays intact; heapsort's worst-case bound caps the whole algorithm. Add an insertion-sort cutoff at small n and you have the std::sort in libstdc++ (since the GCC 3.x era) and in MSVC's STL. libc++ added the depth limit in LLVM 14 (2022)[22]; LLVM 17 (2023) moved it to a pdqsort-derived implementation with branchless partitioning for arithmetic types (§10)[10].
#include <algorithm> // std::iter_swap, std::make_heap, std::sort_heap #include <bit> // std::bit_width (C++20) // Returns whichever of the three iterators points at the median value. template<typename It, typename Compare> It median_of_three(It lowSample, It midSample, It highSample, Compare less) { if (less(*lowSample, *midSample)) { if (less(*midSample, *highSample)) return midSample; // low < mid < high return less(*lowSample, *highSample) ? highSample : lowSample; // mid is the largest } if (less(*lowSample, *highSample)) return lowSample; // mid <= low < high return less(*midSample, *highSample) ? highSample : midSample; // low is the largest } template<typename It, typename Compare> void introsort_loop(It first, It last, int depthBudget, Compare less) { while (last - first > 16) { // Ranges of 16 or fewer wait for the final insertion sort. if (depthBudget == 0) { // Quicksort recursion is going too deep: std::make_heap(first, last, less); // finish this range with heapsort (§7), std::sort_heap(first, last, less); // which is O(n log n) on any input. return; } --depthBudget; It middle = first + (last - first) / 2; std::iter_swap(first, median_of_three(first, middle, last - 1, less)); // Pivot to the front. It cut = hoare_partition(first, last, less); introsort_loop(cut, last, depthBudget, less); // Recurse on the right part... last = cut; // ...and loop on the left, saving a call. } } template<typename It, typename Compare> void introsort(It first, It last, Compare less) { const auto count = static_cast<std::size_t>(last - first); // Musser's budget: 2 * floor(log2 n) levels of partitioning before heapsort takes over. int depthBudget = 2 * (static_cast<int>(std::bit_width(count)) - 1); introsort_loop(first, last, depthBudget, less); insertion_sort(first, last, less); // Every element is now within 16 slots of home: one cheap pass. }
Worked example
Sorting 1,000,000 elements: std::bit_width(1,000,000) is 20, so the budget in the listing is 2 × (20 − 1) = 38 levels of partitioning.
A perfectly balanced quicksort needs about 20 levels, so ordinary inputs finish well inside the budget. An input that keeps forcing lopsided splits uses up the 38 levels on some subarray, and that subarray, and only that one, gets finished by heapsort.
Musser's killer-sequence experiment is worth repeating: he constructed a 100,000-element input designed to defeat median-of-three quicksort and measured introsort's running time at 1/200 of the median-of-three quicksort's[9]. Heapsort takes over only for the subarrays that exhaust the depth budget and finishes them in n log n; the rest of the input keeps quicksort's average-case behavior.
Why 2 log2n?
The constant in front of the log is a tradeoff. A perfectly balanced quicksort recurses exactly log2n deep; a median-of-three quicksort on random data goes somewhat deeper on some branches. The factor 2 gives quicksort room to finish on inputs that are unlucky but not pathological. At 1.0, heapsort would trigger on ordinary inputs; at 4.0, an adversarial input would burn roughly twice as much partitioning work before heapsort took over (the bound stays O(n log n) either way, only the constant grows). Musser suggested 2 ⌊log2n⌋; libstdc++ and libc++ use it, and MSVC allows about 1.5 log2n.
Many equal keys are a weak spot. Hoare partitioning (both cursors stop on elements equal to the pivot) splits a run of equal keys evenly, so it stays n log n, but it still spends n log n work on input that a three-way partition would finish in linear time; a Lomuto partition is worse and goes quadratic. Bentley and McIlroy 1993 popularized the three-way ("fat") partition for this case, and pdqsort gets the same effect with a cheaper trick (§10), one reason it beats plain introsort on inputs with many duplicates.
09Timsort, the natural-runs mergesort
Last frame's sorted event list gets a handful of new events appended, and now needs sorting again. Almost all of it is already in order. A sort that notices that can finish in close to one pass instead of a full n log n. Tim Peters started writing timsort for Python's list.sort in 2002. The design document, Objects/listsort.txt in the CPython repo, is a detailed record of the design decisions and their measurements, and worth reading in full[11]. The premise: real data is often not random. Logs arrive mostly sorted, with a few out-of-order entries. Database query results arrive in chunks that are themselves sorted. Game-engine event streams from the prior frame are usually monotonic in timestamp. A sort that exploits existing order can beat one that ignores it.
Timsort is a stable mergesort tuned for runs. The four moving parts:
- Run detection. Scan left-to-right looking for the longest stretch of consecutive elements that is non-decreasing or strictly decreasing. Reverse the decreasing runs in place (so they become increasing). A "run" is the unit of work.
- Minimum run length (minrun). If the natural run is shorter than minrun, extend it to minrun elements with binary insertion sort. CPython picks minrun between 32 and 64 so that n / minrun is a power of two or slightly less, which keeps the merges balanced; arrays under 64 elements are just binary-insertion-sorted whole[11].
- The merge stack. Push each run onto a stack. After each push, check two Fibonacci-style invariants on the top three runs (X, Y, Z, top of stack last): runlen(X) > runlen(Y) + runlen(Z) and runlen(Y) > runlen(Z). If either is violated, merge Y with the smaller of X and Z, and repeat. This keeps merges roughly balanced and the stack short.
- Galloping merge. When one run keeps winning during a merge (a long stretch of its elements all precede the other run's next element), timsort switches to exponential search to find where the streak ends, so a streak of k wins costs O(log k) comparisons instead of k.
Worked example
Run detection on [1, 2, 3, 9, 8, 7, 4, 5, 6]: 1, 2, 3, 9 is non-decreasing, and 8 breaks it. 8, 7, 4 is strictly decreasing, and 5 breaks it, so it's reversed in place to 4, 7, 8. Then 5, 6. Three runs, merged pairwise.
minrun for n = 2,112: CPython keeps the top 6 bits of n (2,112 = 33 × 64, so they read 33) and adds 1 if any lower bit is set (none is). minrun = 33, and 2,112 / 33 = 64 runs, a power of two, so every merge is between runs of equal length.
The 2015 invariant bug
Stijn de Gouw and colleagues at CWI Amsterdam, using the KeY verification tool (which proves, with human guidance, that Java code meets a formal specification) to prove timsort correct, discovered that the merge stack's invariant was not actually being maintained[14]. mergeCollapse only checked the invariant against the top three runs of the stack. After it merged the top runs and pushed the result back, runs further down the stack could be left in a state that violated the invariant globally. The error did not produce wrong output, but it broke the bound on stack depth: de Gouw's team constructed run-length sequences that overflowed the fixed-size run stack OpenJDK had allocated, so sort() threw ArrayIndexOutOfBoundsException.
Two fixes were available: enlarge the stack to cover the actual worst case under the broken invariant, or fix mergeCollapse so the invariant really holds, as de Gouw's paper proposes. OpenJDK took the first path and enlarged the stack. CPython took the second: its merge_collapse now also checks the fourth run from the top (bpo-23515, committed February 2015, released in 2.7.10 and 3.4.4).
Formal verification of a standard-library sort was practical by 2015, and it found a bug that thirteen years of production use and testing had not. The inner loops of sorts get exercised by every test; the bookkeeping around them (stack invariants, merge ordering, recursion bounds) is read by few and proved by fewer.
10pdqsort, the branchless modern quicksort
On random keys, quicksort's partition loop asks "is this element smaller than the pivot?" and the answer is a coin flip, so the CPU's branch predictor guesses wrong about half the time and throws away work each time. On cheap integer keys that misprediction costs more than the comparison itself. Pattern-defeating quicksort, Orson Peters (the 2021 paper[16] writes up an algorithm that had been shipping since 2017), is a descendant of introsort. It adds three ideas that make it faster than plain introsort on many common inputs[16]:
- BlockQuicksort partitioning. Edelkamp and Weiß 2016[21] showed that on cheap keys the partition's unpredictable branch on the pivot comparison costs more than the comparison itself. Their fix: scan a block of elements (128 in BlockQuicksort, 64 in pdqsort) and record the offsets of the ones on the wrong side in a small buffer, using arithmetic instead of branches; then swap the recorded pairs in a separate pass. libc++'s version records the same information as 64-bit bitsets. Data-dependent mispredictions drop to nearly zero, leaving only predictable loop branches. BlockQuicksort measured an 80% speedup over GCC's
std::sorton random integers. - Pattern defeat. Pdqsort checks whether each partition was badly unbalanced (either side under n/8). If so, it deterministically swaps a few elements at fixed offsets to break up patterns such as organ pipes or sawtooths before continuing. That handles accidental bad inputs, not a determined adversary; for those, after about log2 n bad partitions it falls back to heapsort the way introsort does.
- Equal keys. In every subarray except the leftmost, each element is at least as large as the element just before the subarray, an earlier pivot. If the new pivot equals that earlier pivot, pdqsort partitions into "equal to pivot" and "greater" instead and skips the equal part entirely. With k distinct values the sort runs in O(n · k), linear when k is small.
Pdqsort was Rust's slice::sort_unstable from 2017 until Rust 1.81 (2024) replaced it with ipnsort, a pdqsort descendant by the same author and Lukas Bergdoll[32]; it ships in Boost.Sort, and it is the basis of the branchless std::sort that Google's engineers contributed to libc++ (described in 2022, shipped in LLVM 17, 2023). The libc++ 17 release notes report std::sort getting up to 50% faster for arithmetic types and about 10% faster for other types[22].
The branchless scan is short. The conventional Hoare partition has a data-dependent branch on the pivot comparison, and on random data the predictor is wrong about half the time. BlockQuicksort instead fills two arrays of offsets (the positions of wrong-side elements found in a left block and a right block), then swaps them in pairs. The scan loop has no data-dependent branch because the comparison result is added to a counter instead of being branched on:
template<typename T> void block_scan_left(T* block, T pivot, unsigned char* offsets, int& count) { count = 0; for (int i = 0; i < 64; ++i) { offsets[count] = (unsigned char)i; count += (block[i] >= pivot); // No branch: bool-to-int extends the count. } } // Symmetric block_scan_right. Then a second loop swaps element pairs from the // two offset arrays; that pass has one predictable loop branch and no data-dependent ones.
Worked example
Run the scan above on an 8-element block [7, 2, 9, 5, 1, 6, 3, 8] with pivot 5 (shortened from 64). Every iteration writes its index into offsets[count], then adds 1 to count if the element is ≥ 5.
The elements ≥ 5 are at indices 0, 2, 3, 5 and 7, so count ends at 5 and offsets starts 0, 2, 3, 5, 7. The writes for 2, 1 and 3 were simply overwritten by the next index. No iteration branched on the data.
Combined effect: pdqsort keeps introsort's O(n log n) worst case (both fall back to heapsort), is substantially faster on random integers thanks to the branchless partition, is much faster on inputs with few distinct keys, and runs in linear time on fully ascending, fully descending, and all-equal input, which introsort handles in n log n[16]. Nearly sorted input also benefits: when a partition needed no swaps, pdqsort tries a bounded insertion sort on each side and keeps the result if it finishes quickly.
11Powersort: timsort with a proof
Timsort finds the runs, but then has to decide which runs to merge first, and a bad order can do noticeably more copying than necessary. Munro and Wild's 2018 paper "Nearly-Optimal Mergesorts"[15] attacked the part of timsort that even Tim Peters described as a heuristic: the merge policy. Timsort's stack-invariant check is a pragmatic rule that usually produces balanced merges, with no optimality guarantee. Powersort replaces it with a rule derived from Mehlhorn's nearly optimal binary-search-tree construction: give each boundary between adjacent runs a power based on where it falls in the array, and merge pending runs whose boundary power is greater than that of the newest boundary.
The result is a stable mergesort whose total merge cost is provably within an additive O(n) of the optimum for the given runs (measured by the entropy of the run lengths). Timsort's policy has no such guarantee and can be measurably worse on some run-length patterns; on typical inputs the two are close. Tim Peters merged powersort into CPython in September 2021 (gh-78742 / PR #28108), shipping in Python 3.11 in October 2022[23]. The patch kept the rest of timsort (run detection, minrun, binary insertion sort, galloping) intact and swapped only the merge-trigger rule. PyPy, Apple's WebKit, and AssemblyScript also use powersort.
Worked example
An 8-element array with a run of 3 followed by a run of 5. Their midpoints are at 1.5 and 5.5, or 0.1875 and 0.6875 of the array. In binary those are 0.0011 and 0.1011, which differ in the first bit after the point, so the boundary has power 1: it sits at the root of a balanced merge tree and is merged last.
Two runs of 2 at the start of the same array have midpoints 1/8 and 3/8, binary 0.001 and 0.011, which first differ in bit 2: power 2, one level down, merged earlier.
For a new run-adaptive stable sort, the powersort policy is a sensible default. Many existing timsort ports (Java's object sort among them) still use the original heuristic, because on typical inputs the difference is small.
What is a "power" of a run boundary?
Take two adjacent runs and express the midpoint of each as a fraction of the array length: a = (s1 + n1/2) / n and b = (s2 + n2/2) / n, where s is a run's start and ni its length. Write both in binary. The power of the boundary between the runs is the first bit position after the binary point where a and b differ. A boundary whose runs straddle the array's midpoint gets power 1; one straddling the quarter or three-quarter point gets power 2, and so on. The power is the depth at which that boundary would sit in a balanced merge tree, power 1 being the root, the last merge.
The merge rule: when a new run is found, compute the power of the boundary in front of it, merge pending runs on the stack while their saved power is greater than the new power (deeper boundaries merge first), then push. This builds, on the fly, a merge tree over the runs that is balanced by length. Mehlhorn 1977 proved that the analogous bisection construction for binary search trees has a weighted path length within an additive constant per unit weight of the optimum[24], which is where powersort's guarantee comes from.
The difference from timsort: timsort decides whether to merge by comparing the lengths of the top three or four runs on its stack. Powersort decides from where each boundary falls in the whole array, which is what makes its merge tree provably close to optimal.
12Radix sort: linear time, no comparisons
The draw-call keys from §1 are plain 32- or 64-bit integers, so sorting them doesn't need comparisons at all: you can sort by their bytes directly. Radix sort is a strong answer for "I have a million 32-bit keys and I want them sorted." It runs in O(d · n) where d is the number of digits (bytes, or whatever radix you pick), reads its input in sequential streams, and parallelizes well across cores or GPU threads. The catch is that keys must break into digits: fixed-width integers, floats reinterpreted as integers, or strings (with the MSD variant). Many renderers use it for draw-call sorting (§16).
Two flavors. LSD radix sort is the usual choice for fixed-width numeric keys: sort by the low byte first, then the next byte, and so on. Each pass is a stable counting sort into 256 buckets (for a byte radix). After four passes on 32-bit keys the array is fully sorted, because each pass is stable: keys that tie on this pass's byte keep the order the earlier, lower-byte passes gave them. MSD radix sort is the variant for strings and variable-length keys.
Worked example
Sort the 16-bit keys 0x0201, 0x0102, 0x0101, 0x0202 one byte at a time.
Pass 1, low byte: the keys ending 01 go first, in their original order (0x0201, 0x0101), then those ending 02 (0x0102, 0x0202).
Pass 2, high byte: high byte 01 first, keeping pass 1's order (0x0101, 0x0102), then 02 (0x0201, 0x0202). Sorted, with no comparisons between keys.
void radix_sort_u32(uint32_t* keys, uint32_t* scratch, int count) { uint32_t* src = keys; uint32_t* dst = scratch; for (int passShift = 0; passShift < 32; passShift += 8) { int bucketCount[256] = {0}; // Pass 1: count how many keys go in each bucket. for (int i = 0; i < count; ++i) ++bucketCount[(src[i] >> passShift) & 0xFF]; // Prefix sum: turn counts into starting offsets. int total = 0; for (int digit = 0; digit < 256; ++digit) { int keysWithDigit = bucketCount[digit]; bucketCount[digit] = total; total += keysWithDigit; } // Pass 2: scatter keys into dst at their bucket offsets. Scanning src in // order keeps equal digits in order, which is what makes LSD radix correct. for (int i = 0; i < count; ++i) { int bucket = (src[i] >> passShift) & 0xFF; dst[bucketCount[bucket]++] = src[i]; } std::swap(src, dst); // The next pass reads what this pass wrote. } // Four passes is an even number of swaps, so the result is already back in // keys; the copy only matters if the pass count is changed to an odd number. if (src != keys) std::memcpy(keys, src, count * sizeof(uint32_t)); }
Production radix sorts add what this listing skips: a payload (you sort key+index pairs or key+value structs, not bare keys); a skip check per pass (if one bucket holds all n elements the byte is constant and the whole pass can be skipped, common for the high bytes of small keys); the float sign-flip from the next section; and per-thread histograms for the multicore and GPU versions.
Cost: each pass reads the array once to build the histogram, then reads it again and writes it once to scatter, so roughly 3n memory operations per pass and ~12n across the four passes (count the loops in the listing above). The reads are sequential; the scatter writes go to 256 separate streams, which caches and write-combining handle well at this width. If memory bandwidth is the limit, 48 bytes of traffic per 4-byte key at 16 GB/s is roughly 3 ns/key for the whole sort. A comparison sort of a million keys typically costs tens of nanoseconds per key. For small arrays the fixed setup (four 256-entry histograms, four passes regardless of n) hands the win back to the comparison sort; published radix sorts such as ska_sort switch to std::sort below about 128 elements.
Sorting floats with a radix sort
Radix sort handles depth keys because non-negative IEEE 754 floats, reinterpreted as 32-bit unsigned integers, sort in the same order as the floats. Negative values need a fix-up of a few lines: flip every bit of a negative float and only the sign bit of a non-negative one, and the whole range sorts correctly.
Worked example
1.0 is 0x3F800000; flip the sign bit and it becomes 0xBF800000. −1.0 is 0xBF800000; flip every bit and it becomes 0x407FFFFF. −2.0 is 0xC0000000, which becomes 0x3FFFFFFF.
As unsigned integers: 0x3FFFFFFF < 0x407FFFFF < 0xBF800000, the same order as −2 < −1 < 1.
Aras Pranckevičius's "Rough sorting by depth" post is a widely cited write-up of using the top bits of a float as a packed depth field[26]: since larger positive floats give larger integers, the top bits drop straight into a sort key. He keeps the top 10 bits; the sign bit is always zero for positive depths, so 9 of them vary, which works out to about seven buckets per factor of ten in distance (0.01 maps to 240, 1000 to 273). That coarseness is deliberate: front-to-back ordering of opaque draws only needs to be rough, since a misordered draw costs some overdraw, and coarse buckets leave room to sort by render state inside each one. Transparent draws that must blend in order need many more depth bits.
13Counting sort: when the key range is tiny
Particles come in 16 priority levels and you want them grouped by level every frame. With only 16 possible keys, you don't need to sort at all in the usual sense: count how many particles have each level, and you know exactly where each group starts. Counting sort is the inner pass radix sort wraps. Given an array of n keys, each in [0, k), sort in O(n + k): count occurrences of each value, prefix-sum the counts, scatter elements into output. When k = O(n) the cost is linear; when k is much larger than n the histogram-allocation cost dominates and counting sort loses to a comparison sort.
Worked example
Keys [2, 0, 3, 2, 1, 0], each in [0, 4).
Count: key 0 appears 2 times, key 1 once, key 2 twice, key 3 once: [2, 1, 2, 1]. Prefix-sum into starting offsets: [0, 2, 3, 5].
Scatter in input order: the first 2 goes to slot 3, the 0 to slot 0, the 3 to slot 5, the second 2 to slot 4, the 1 to slot 2, the last 0 to slot 1. Result [0, 0, 1, 2, 2, 3], stable, in two passes over the data.
Use cases in engines:
- Particle priority bucketing. A particle system with 4-bit priority gives 16 buckets; one counting pass groups particles per frame in O(n).
- Material ID grouping. If material IDs are dense in [0, 256), counting sort by material ID puts every draw call of the same material together with one pass.
- Histogram-based effects. Auto-exposure's luminance histogram is the counting half of a counting sort on log-luminance; its prefix sums give the percentiles the exposure logic needs.
Java's Arrays.sort switches to counting sort for byte arrays longer than 64 elements and char or short arrays longer than 1,750, because the key ranges (256 and 65,536 values) make the histogram cheap once it is amortized over enough elements[35]. For int and wider types it uses dual-pivot quicksort, since a histogram over 4 billion values is out of the question.
14Bitonic sort and the GPU
A GPU particle system has its particles in GPU memory already, and copying them back to the CPU to sort would cost more than the sort. The sort has to run on the GPU. Quicksort and a sequential mergesort make one decision at a time, and a GPU wants thousands of threads doing identical work in lockstep. Two families fit: radix sorts built on parallel prefix sums (each pass's histogram and scatter split cleanly across threads; GPU sorts of large key arrays, such as the one in CUDA's CUB library, are usually radix sorts), and sorting networks, where which position compares with which is fixed ahead of time. Ken Batcher's 1968 bitonic sort[27] is the classic sorting network.
The structure: a bitonic sequence is one that increases then decreases (or a rotation of one). One layer of n/2 parallel compare-and-swaps, pairing element i with element i + n/2, splits a bitonic sequence into two bitonic halves with every element of the first no larger than any element of the second; repeating on the halves sorts it in log2 n layers (the "bitonic merge"). Bitonic sort builds bitonic sequences by sorting halves in opposite directions and merging, recursively. Total operations: O(n log²n). Depth (the longest chain of dependent layers): O(log²n). With enough threads, depth matters more to wall time than total work.
Bitonic sort's cost summary versus the CPU sorts:
| Sort | Total work | Parallel depth | In place | Stable |
|---|---|---|---|---|
| quicksort (serial) | O(n log n) | O(n log n) | yes | no |
| mergesort (serial) | O(n log n) | O(n log n) | no | yes |
| radix sort (serial) | O(d·n) | O(d·n) | aux | yes |
| bitonic sort (parallel) | O(n log²n) | O(log²n) | yes | no |
| GPU radix sort | O(d·n) | O(d log n) | aux | yes |
Bitonic sort does more total work than mergesort (n log²n vs n log n) but every compare-and-swap in a layer is independent. Sorting 4096 elements takes 78 layers of 2,048 compare-and-swaps each; a serial mergesort needs about 50,000 dependent comparisons. The extra work buys a schedule with no data-dependent control flow. GPU Gems 2, chapter 46, describes a GPU implementation[28]. For large arrays radix sort usually wins on the GPU as well: Unreal depth-sorts its GPU particles with a compute-shader radix sort (GPUSort.cpp and RadixSortShaders.usf in the engine source).
15Live race: every sort, side by side
The sections above made claims about which sort wins on which data. This widget puts six of them on identical input so you can check. Six sorts run on the same input, animated as bar charts and paced by the work each one does. Pick the input shape to see how each algorithm responds to sorted, reverse-sorted, mostly sorted, and few-unique inputs, then press "Run race":
16Engine case: sorting draw calls
Most renderers sort their draw calls before submitting them. State changes (binding a new shader, texture, or vertex buffer) cost CPU time in the driver and can stall the GPU, and the cost is per change, not per call. Five thousand draw calls in arbitrary order can mean thousands of shader changes; the same calls sorted by shader need only as many changes as there are distinct shaders. A per-frame sort is a cheap way to get that back.
Christer Ericson's 2008 pattern[1], still widely used, packs everything that matters into a single 64-bit sort key. One possible layout for opaque draws:
Worked example
An opaque draw on render target 0 with shader 5, material 300, depth bucket 0x123456 and sequence number 7.
Shift each field to its place and OR them: (5 << 48) | (300 << 32) | (0x123456 << 8) | 7 = 0x0005012C12345607. Reading the hex left to right gives the fields in priority order: 0005 (target 0, opaque, shader 5), 012C (material 300), 123456 (depth), 07.
The bit order encodes the sort hierarchy: render target first, then the opaque/transparent split, then shader, then material, then a depth bucket. For opaque draws the depth field holds the depth bits directly, so draws sharing a shader and material come out front to back and early-Z rejects more hidden pixels. Transparent draws must be blended back to front across all of them, so for those the key uses a different layout: depth, bit-inverted so that far sorts first, moves above shader and material. Ericson describes exactly this swap of the depth and material fields. One sort then produces both orderings.
Once the key is packed, any integer sort works, and at thousands of keys a radix sort is a common choice. Unreal's core library includes RadixSort32, a stable radix sort on 32-bit keys[25], and its renderer packs mesh draw commands into 64-bit FMeshDrawCommandSortKey values[36]. Bevy tried swapping its comparison sorts for the radsort crate in 2022: the median sort_phase_system time on the many_cubes benchmark dropped from 0.728 ms to 0.094 ms, but the same change made it roughly ten times slower on two sprite benchmarks (0.184 to 1.95 ms on bevymark, 0.106 to 1.19 ms on many_sprites), a regression the issue left unexplained[2]. Measure on your own workload before switching.
17Engine case: sort-and-sweep broadphase
Collision detection's broadphase finds candidate pairs of objects whose AABBs overlap. The naive algorithm is n²; sweep-and-prune reduces it to roughly n log n per frame by sorting AABB endpoints along an axis and sweeping a moving "active list" across them[29].
The sort here is interesting because the input is almost sorted from frame to frame. Object positions change a little per frame; the endpoint list mostly preserves order from the previous frame. Insertion sort costs O(n + s) for s out-of-order pairs, which beats a general n log n sort on this workload. With 10,000 endpoints of which 200 pairs swapped order since last frame, that's about 10,000 + 200 = 10,200 steps, against roughly 133,000 comparisons (10,000 × log2 10,000) for a sort from scratch. Incremental sweep-and-prune implementations exploit it: Bullet's btAxisSweep3 keeps last frame's sorted endpoint arrays and moves each changed endpoint up or down into place, updating the overlap pairs as endpoints pass each other[33].
Some physics engines skip sort-and-sweep entirely. Box2D's broadphase uses b2DynamicTree, an incrementally updated AABB tree; version 3 picks each new leaf's sibling and its tree rotations by surface area (perimeter, in 2D)[34], the cost model BVH builders use[30]. The ordering work doesn't disappear; it moves inside the data structure, and the tree's incremental updates fill the role of an explicit per-frame sort.
18Picking the right sort
When you're about to call a sort in engine code, start from what you know about the data: how many items, what the key is, whether order already exists, where the data lives. The decision table:
| Workload | Right answer | Why |
|---|---|---|
| Generic C++, types with cheap compare | std::sort (introsort / pdqsort) | Fast on average, n log n worst case, in place, library-provided. |
| Generic C++, types with expensive compare | a merge-based sort (std::stable_sort, timsort) | Close to the minimum number of comparisons, about n log₂ n, versus roughly 1.2 to 1.4 n log₂ n for quicksort variants. |
| Generic, must be stable | std::stable_sort (a mergesort in libstdc++, libc++, and MSVC) | The unstable sorts don't preserve equal-key order. |
| Real data, often partially sorted | timsort (Python, Java, V8) or powersort | Adaptive: O(n) on already-sorted input, and close to linear when the data is a few long runs. |
| Bounded integer keys, n > 100 | radix sort (LSD) | Linear time, no comparisons, parallelizes well. Common for renderer sort keys. |
| Small integer range (k no larger than about n) | counting sort | One counting pass and one scatter, no comparisons. Java does this for large byte, char, and short arrays. |
| n < 32, any keys | insertion sort | Recursive sorts pay more overhead than the inner-loop work at this scale. |
| Worst-case latency budget (real-time) | heapsort or introsort | Guaranteed n log n; quicksort alone can blow the budget on bad input. |
| Data on GPU | bitonic sort or GPU radix | Both fit GPU parallelism. Radix usually wins for large arrays of fixed-width keys; bitonic suits small batches and arbitrary comparisons. |
| Data on disk, larger than RAM | external mergesort | Sequential I/O; a k-way merge needs only logk of the run count in passes over the data. |
| Strings of varied length | MSD radix or three-way radix quicksort | Looks at each character of the distinguishing prefixes a small number of times instead of re-comparing shared prefixes on every comparison. |
std::sort is the right default for most sorts. The exceptions are large sorts that run every frame on keys that pack into integers (draw calls, particles) and sorts of nearly sorted data (the broad phase), which is where the case studies above come from.
19Pitfalls
Use this as a review checklist. Each item is a sort bug that turns up in production code, and most of them pass tests on small, friendly inputs:
- Non-strict weak ordering.
std::sortrequires a comparator that is a strict weak order: irreflexive (!(a < a)), asymmetric (a < b ⇒ !(b < a)), transitive (a < b ∧ b < c ⇒ a < c), and the equivalence derived from "neither is less than the other" must be transitive too. Violations are undefined behavior; in practice they show up as out-of-bounds reads and crashes (libstdc++'s unguarded partition loops rely on the ordering to stop) or as unsorted output. A common bug: comparing floats where one might be NaN. Every comparison with NaN is false, so NaN is "equivalent" to everything and equivalence stops being transitive. - Unstable when you needed stable.
std::sortis allowed to reorder equal elements;std::stable_sortis not. A multi-pass sort (sort by depth, then by material, to get material-major order with depth inside each material) only works if the later passes are stable. The bug shows up as flickering: equal keys come out in a different order from frame to frame, so overlapping sprites swap places. - Comparator state. Comparators with mutable state (a counter, a cache) break the assumption that the order is fixed. The sort may call the comparator more than once on the same pair, in any order, and
std::sorttakes the comparator by value and may copy it, so state can end up split across copies. Stateful comparators that give inconsistent answers can crash the sort; ones that stay consistent but mutate are hard to debug. - Integer overflow in the comparator. In a
qsort-style three-way comparator, return a - b; is only safe when the difference fits and is an integer. For 32-bit ints spanning more than half the range it overflows and flips sign: with a = 2,000,000,000 and b = −2,000,000,000, a − b is 4,000,000,000, which wraps to −294,967,296 and says a < b. For floats converted to an int result it truncates small differences to 0. Write return (a > b) - (a < b); instead. - Sorting a container that mutates during the sort. Iterators invalidate when the underlying container resizes. The sort can corrupt memory if a comparator triggers a container modification, for example a comparator that calls into code that loads an asset and appends to the array being sorted.
- The 2006 Java binary-search overflow. Joshua Bloch reported that the (lo + hi) / 2 in Java's binary search overflows for arrays of 230 or more elements[17]. The same bug appears in any mergesort midpoint that uses the naive formula; lo + (hi − lo) / 2 avoids it.
- Allocating a merge buffer in the inner loop. A mergesort that
new[]s its scratch buffer for every recursive call costs more in allocation than it saves in algorithmic work. Allocate once at the top. - Sorting pointers when the indirection costs more than the sort. A sort that compares
a->materialagainstb->materialdereferences twice per compare. Sorting 10,000 elements takes on the order of 150,000 comparisons; if those dereferences miss cache at around 30 ns each, the pointer chasing alone costs milliseconds. Pack the sort key into the array directly (the draw-call key trick).
20What's next
Next in the series, x86-64 Assembly goes below the C++ to the instructions the CPU runs: registers, calling conventions, branches and the out-of-order core, which is where branchless partitions like pdqsort's earn their speed. Beyond sorting itself, the natural follow-ups, in roughly increasing depth:
- Selection algorithms. "Find the k-th smallest" without sorting the whole array. Quickselect partitions like quicksort but recurses into only one side, for expected O(n). Median-of-medians (BFPRT, 1973) gives a deterministic linear-time selection. The introselect fallback in Musser 1997 is to selection what introsort is to sorting.
- External-memory sorting. Data larger than RAM. k-way merge sort plus a tape-or-disk layout. The classic algorithm; on NVMe SSDs bandwidth matters more than seek time, which changes the tuning.
- Parallel and concurrent sorts. Multi-way mergesort with work stealing, parallel quicksort, GPU radix sort. The work-span model (as in Cilk) for analyzing them. The job systems tutorial introduces the runtime; the parallel-sort algorithms layer on top.
- Top-k and partial sort. When you don't need the whole order, just the smallest k.
std::partial_sortis typically heap-based (O(n log k)); when k is a large fraction of n,std::nth_elementfollowed by sorting the first k is usually faster. - Sorting under adversarial input. McIlroy's adversary (§5) shows how an attacker who controls the input can drive a deterministic quicksort quadratic. Introsort's depth limit or pdqsort's heapsort fallback caps the damage at O(n log n); randomized pivots make the attack depend on guessing the random state.
- Cache-oblivious sorting. Sorting N items with a cache of size M and blocks of size B needs Θ((N/B) · logM/B(N/B)) block transfers; Frigo et al.'s funnelsort meets that bound without knowing M or B[31]. It is the model to use when the data is far larger than cache.
The most useful next step is empirical: profile your renderer's draw-call sort. If its comparator dereferences pointers or compares strings, pack an integer key, then measure a radix sort against std::sort on the packed keys.
Sources
- Christer Ericson. "Order your graphics draw calls around!" realtimecollisiondetection.net blog, October 2008. realtimecollisiondetection.net. The widely cited write-up of bit-packed draw-call sort keys (layer, viewport, translucency, depth, material), including swapping the depth and material fields for translucent draws.
- Bevy Engine. "Use radix sort for sort phase and sprite sorting." GitHub issue #4291, 2022. github.com/bevyengine/bevy/issues/4291. Source for the 0.728 ms → 0.094 ms median
sort_phase_systemtime on many_cubes and the regressions on the bevymark and many_sprites benchmarks. Bevy 0.8 shippedradsortfor its 3D phase sorts; later releases moved opaque meshes to unsorted bins. - Peter Norvig. "Teach Yourself Programming in Ten Years," "Approximate timing for various operations" table. norvig.com/21-days.html. Memory-hierarchy latency ballparks used to estimate per-comparison cost: L1 ~0.5 ns, branch mispredict ~5 ns, DRAM ~100 ns.
- Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998. Chapters 5.1 to 5.3 cover the history of mergesort, the analysis of comparison-based sorting, and the lower-bound proof.
- C. A. R. Hoare. "Quicksort." The Computer Journal 5(1):10–16, 1962. comjnl 5.1.10. The full quicksort paper, with the analysis; it follows Hoare's Algorithms 63 and 64 in Communications of the ACM 4(7), July 1961.
- J. W. J. Williams. "Algorithm 232 - Heapsort." Communications of the ACM 7(6):347–348, 1964. dl.acm.org/doi/10.1145/512274.512284. The original heapsort paper; also introduces the binary heap as a standalone data structure.
- Robert W. Floyd. "Algorithm 245 - Treesort 3." Communications of the ACM 7(12):701, 1964. The bottom-up heap-construction algorithm that brings heapify from O(n log n) to O(n).
- Jon L. Bentley, M. Douglas McIlroy. "Engineering a Sort Function." Software: Practice and Experience 23(11):1249–1265, November 1993. PDF. The paper FreeBSD's
qsortdescends from; adopts Tukey's pseudomedian of nine for large arrays and a split-end three-way partition for equal keys. - David R. Musser. "Introspective Sorting and Selection Algorithms." Software: Practice and Experience 27(8):983–993, August 1997. PDF. The introsort paper: the 2 ⌊log2n⌋ depth budget, heapsort's 2 to 5 times slower average, and the median-of-3 killer experiment (introsort at about 1/200 of median-of-three quicksort's time on 100,000 elements).
- LLVM Project. "libcxx
std::sort." Implementation inlibcxx/include/__algorithm/sort.h. github.com/llvm/llvm-project. Source for the current insertion-sort cutoff (24), the 2 log2n depth budget, and the pdqsort-derived structure (the LLVM 14 to 16 versions of this file used cutoffs of 30 for trivially copyable types and 6 otherwise). - Tim Peters. listsort.txt, the timsort design document. CPython repository,
Objects/listsort.txt. github.com/python/cpython. Source for the minrun-in-[32, 64] choice, the merge-stack Fibonacci-style invariants, galloping mode, and the empirical motivation (real-world inputs are not random). - Vladimir Yaroslavskiy. "Dual-Pivot Quicksort algorithm." Proposal to the OpenJDK core-libs mailing list, 2009. PDF (archived). The dual-pivot quicksort that became
java.util.Arrays.sortfor primitive types in Java 7 (JDK-6880672). - Bernhard Beckert, Jonas Schiffl, Peter H. Schmitt, Mattias Ulbrich. "Proving JDK's Dual Pivot Quicksort Correct." Verified Software: Theories, Tools, and Experiments (VSTTE), 2017. PDF. The KeY-based formal verification of Yaroslavskiy's algorithm; turns "we believe this works" into a machine-checkable proof.
- Stijn de Gouw, Jurriaan Rot, Frank S. de Boer, Richard Bubel, Reiner Hähnle. "OpenJDK's java.utils.Collection.sort() is broken: The Good, the Bad and the Worst Case." Computer Aided Verification (CAV), 2015. The discovery of the timsort stack-invariant bug that had been in production since 2002; CPython fixed
merge_collapseand OpenJDK enlarged its run stack as a result. envisage-project.eu summary. - J. Ian Munro, Sebastian Wild. "Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs." European Symposium on Algorithms (ESA), 2018. arXiv:1805.04154. The powersort paper. Its merge policy is used by CPython 3.11 and later, PyPy, AssemblyScript, and Apple's WebKit.
- Orson Peters. "Pattern-defeating Quicksort." arXiv preprint, June 2021. arXiv:2106.05123. The pdqsort paper: block partitioning, deterministic pattern-breaking shuffles, the equal-key partition, and linear time on sorted, reverse-sorted, and all-equal input. Rust's
slice::sort_unstablefrom 2017 until Rust 1.81 (2024); ships in Boost.Sort. - Joshua Bloch. "Nearly All Binary Searches and Mergesorts are Broken." Google Research Blog, June 2006. ai.googleblog.com. Reports that (lo + hi) / 2 overflows for arrays of 230 or more elements, a bug that had been in the JDK's binary search for nine years and in Programming Pearls, and gives the fixes.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th ed., MIT Press, 2022, chapter 8 "Sorting in Linear Time," §8.1 "Lower bounds for sorting." The standard textbook presentation of the decision-tree lower bound.
- Lester R. Ford, Selmer M. Johnson. "A Tournament Problem." The American Mathematical Monthly 66(5):387–389, May 1959. Merge insertion sort, which matches the ⌈log2 n!⌉ comparison lower bound for every n up to 11.
- M. Douglas McIlroy. "A Killer Adversary for Quicksort." Software: Practice and Experience 29(4):341–344, April 1999. PDF. Shows that for essentially any deterministic pivot rule, an adversary can construct input forcing quadratic time: the attack that introsort's heapsort fallback (1997) already guards against.
- Stefan Edelkamp, Armin Weiß. "BlockQuicksort: Avoiding Branch Mispredictions in Quicksort." European Symposium on Algorithms (ESA), 2016. arXiv:1604.06697. The block-partition technique that pdqsort builds on; reports an 80% speedup over GCC's
std::sorton random integers. - Danila Kutenin. "Changing std::sort at Google's Scale and Beyond." danlark.org blog, April 2022. danlark.org. The Google team's write-up of the libc++ sort changes, including the introsort depth limit released in LLVM 14. The shipped speedup figures (up to 50% for arithmetic types, about 10% for other types) are from the libc++ 17 release notes.
- CPython issue gh-78742 / Pull Request #28108. "Use Powersort merge strategy." Author: Tim Peters; merged September 6, 2021; shipped in Python 3.11 (October 2022). github.com/python/cpython/pull/28108.
- Kurt Mehlhorn. "A best possible bound for the weighted path length of binary search trees." SIAM Journal on Computing 6(2):235–239, 1977. The nearly-optimal binary-search-tree construction whose principle powersort applies to merge ordering.
- Epic Games. "RadixSort32." Unreal Engine documentation. dev.epicgames.com. API reference for the stable, comparison-free 32-bit radix sort in Unreal's core library.
- Aras Pranckevičius. "Rough sorting by depth." aras-p.info blog, January 2014. aras-p.info. Using the top 10 bits of a positive float's bit pattern as a coarse depth field in a sort key.
- Kenneth E. Batcher. "Sorting networks and their applications." Proc. AFIPS Spring Joint Computer Conference, 1968, pp. 307–314. PDF. The original bitonic sort paper and the foundational sorting-network reference.
- Peter Kipfer, Rüdiger Westermann. "Improved GPU Sorting." GPU Gems 2, chapter 46, NVIDIA, 2005. developer.nvidia.com. A GPU sorting-network implementation (bitonic and odd-even merge sort) and its optimizations.
- Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, Madhav K. Ponamgi. "I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments." Proc. ACM Interactive 3D Graphics, 1995. The standard reference for sweep-and-prune with incremental re-sorting that exploits frame-to-frame coherence.
- Ingo Wald, Solomon Boulos, Peter Shirley. "Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies." ACM Transactions on Graphics 26(1), 2007. Uses the surface-area heuristic cost model (MacDonald and Booth, 1990) to build and update BVHs over moving geometry.
- Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran. "Cache-Oblivious Algorithms." Proc. 40th IEEE FOCS, 1999. PDF. Funnelsort, which meets the O((N/B) · logM/B(N/B)) block-transfer bound for sorting (first established by Aggarwal and Vitter in the external-memory model) without knowing the cache parameters.
- Lukas Bergdoll, Orson Peters. "Replace sort implementations." rust-lang/rust pull request #124032, merged June 2024; shipped in Rust 1.81, September 2024. github.com/rust-lang/rust/pull/124032. The change that retired pdqsort as
slice::sort_unstable, replacing it with ipnsort (and the stable sort with driftsort). - Erwin Coumans et al.
btAxisSweep3Internal.h, Bullet Physics SDK source. github.com/bulletphysics/bullet3. Incremental sweep-and-prune:sortMinDown,sortMaxUpand friends move each changed endpoint into place in the persistent sorted arrays. - Erin Catto.
dynamic_tree.c, Box2D v3 source. github.com/erincatto/box2d. The dynamic AABB tree behind Box2D's broadphase: sibling selection by the surface-area heuristic and perimeter-reducing tree rotations. - OpenJDK.
java/util/DualPivotQuicksort.java. github.com/openjdk/jdk. Current thresholds: insertion sort up to 44 elements, counting sort for byte arrays over 64 elements and char or short arrays over 1,750. - Epic Games. "FMeshDrawCommandSortKey," Unreal Engine API reference. dev.epicgames.com. The 64-bit packed sort key (a union of base-pass, translucent, and generic layouts) for Unreal's visible mesh draw commands.