All tutorials Mighty Professional
Build a Game Engine · Foundations

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.

Time~70 min LevelJunior to mid; review for senior PrereqsYou can read C++ or pseudocode at intermediate level. Big O notation (read the prior tutorial if it feels rusty). HardwareNone, but a feel for cache and branch prediction helps in §10 and §16.
◂ Build a Game Engine Phase 0 · Foundations Next · x86-64 Assembly ▸
What you'll be able to do by the end

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:

Live · Comparison vs radix at frame scale
comparison sort
···
radix sort (4 pass)
···
frame budget at 60 fps
16.67 ms
The red curve is the comparison sort and the green one the radix sort, with the 60 fps frame budget dashed across the top; drag the draw-call count and the per-comparison cost, and read both costs below. At the defaults (5,000 draws, 30 ns) they read 1.84 ms and 0.062 ms. Both curves are cost models, not measurements. The comparison curve assumes every compare pays for a memory access; with keys packed into the array and data hot in L1, a compare costs a few nanoseconds (mostly branch mispredictions), so drag the slider toward its 5 ns minimum and the crossover moves right. The radix curve assumes a 32-bit packed key with one byte per pass; widening to 64 bits and 8 passes doubles its slope but does not change the shape.

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
1945
John von Neumann describes merge sort.[4] One of the first programs written for a stored-program computer, the EDVAC. Each merge level is one linear pass and there are log2n levels, so the cost is n log n. Stable, awkward to do in place, friendly to sequential storage such as tape. Knuth's Art of Computer Programming vol. 3 traces the lineage.
1959
Shell sort. Donald Shell publishes a gap-decreasing insertion sort variant. Its complexity depends on the gap sequence and is still not fully understood, but it was one of the first in-place sorts to run well below n² in practice. It still turns up in embedded code for its small footprint.
1961
Tony Hoare publishes quicksort.[5] First appears as Algorithm 64 in Communications of the ACM, July 1961; the analysis paper follows in The Computer Journal the next year. Hoare devised it in 1959 as a visiting student at Moscow State University, where he studied probability under Kolmogorov, while working on a Russian-English machine translation project for the UK's National Physical Laboratory. The partition step swaps elements around a pivot until the array is split into "less than pivot" and "greater than pivot." Expected n log n, worst case n². The worst case will matter in §5.
1964
Williams introduces heap sort. Floyd fixes the build.[6] J.W.J. Williams publishes heapsort in Communications of the ACM. Robert Floyd publishes a bottom-up heap-construction algorithm in the same year that brings the build cost from O(n log n) down to O(n)[7]. In-place, guaranteed n log n, cache-hostile.
1993
Bentley and McIlroy engineer the qsort that ships.[8] "Engineering a Sort Function" in Software: Practice and Experience. Pseudomedian-of-nine pivot selection, three-way partition (less than, equal to and greater than the pivot) for the Dutch-national-flag problem of many equal keys, explicit small-array fallback. FreeBSD's qsort and a generation of C library sorts descend from this paper.
1997
Musser publishes introsort.[9] "Introspective Sorting and Selection Algorithms" gives quicksort a worst-case guarantee: monitor recursion depth, switch to heapsort once it exceeds 2 log2n. Worst case becomes n log n, average case stays at quicksort's constant. libstdc++ 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].
2002
Tim Peters writes timsort.[11] Adaptive natural-runs mergesort for CPython's 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).
2009
Yaroslavskiy's dual-pivot quicksort enters the JDK.[12] Vladimir Yaroslavskiy proposes a quicksort variant with two pivots that partitions into three regions per call. Java 7's Arrays.sort for primitive types adopts it. Verified correct in 2017 using the KeY proof tool[13].
2015
The timsort stack-invariant bug.[14] Stijn de Gouw et al. prove, while trying to verify timsort in KeY, that the merge-collapse invariant was wrong. Java's implementation throws 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.
2018
Munro and Wild publish powersort.[15] "Nearly-Optimal Mergesorts" gives timsort a merge policy with provable optimality up to an additive linear term. CPython 3.11 swaps timsort's merge heuristic for the powersort rule in 2022; PyPy, AssemblyScript, and Apple's WebKit also use it.
2021
Orson Peters publishes the pdqsort paper.[16] Pattern-defeating quicksort: introsort plus block partitioning (Edelkamp and Weiß's BlockQuicksort, used when the comparison is cheap and branchless), element shuffling after bad partitions, and a partition trick that skips runs of keys equal to the previous pivot. The paper trails the code by years: Rust had already adopted pdqsort for 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].
2026
The sorts that ship. A modern engine typically ends up with three or four routines: introsort or pdqsort for general comparison sorting, a stable sort where order of equal keys matters, radix sort for fixed-width keys (draw calls, particles), and a GPU sort (radix for large arrays, bitonic networks for small fixed-size batches) for data that already lives on the GPU. The choice depends on the shape of the data and the memory it lives in more than on which sort is fastest in the abstract.

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]:

eq. 1 · the lower bound T(n) ≥ log2(n!) ≥ log2((n/e)n) = n log2(n) − n log2(e) = Ω(n log n)

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:

Live · The decision tree for n = 3
leaves needed
3! = 6
min height
⌈log₂6⌉ = 3
path to this leaf
3
Each inner node is one comparison and each leaf one of the six orderings of a, b and c. Pick an ordering in the dropdown to highlight the comparisons that lead to it, and read the path length below. Any comparison sort on three elements needs a tree with at least six reachable leaves, so some input costs it three comparisons; this tree reaches two of its leaves in two. The worst case is the tree's height. For n = 3 the optimum is 3 comparisons; for n = 10 the bound is ⌈log2(10!)⌉ = 22 and 22 is achievable. Ford and Johnson's 1959 merge insertion sort matches ⌈log2 n!⌉ for every n up to 11[19]; it is rarely used because its bookkeeping costs more than the comparisons it saves.
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.

insertion sort · C++
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:

Live · Where insertion sort beats quicksort
crossover n
···
insertion at n=16
···
quick at n=16
···
Each array size gets two bars, insertion sort and quicksort, measuring the same input. Press Run race, then switch the input shape and run again; the readouts give the crossover size and both costs at n = 16 (126 against 192 on random input). Cost is counted in array reads and writes, not time, and the quicksort's function-call overhead isn't charged, so real crossovers sit somewhat higher than the one shown (24 on random input). Switch input shape to see the crossover move: insertion sort never loses on already-sorted input (it runs in linear time), and on "few unique" it stays ahead longer because this Lomuto quicksort handles duplicate keys badly. Cutoff sizes used in production: libstdc++ below 16, current libc++ below 24 (30 for trivially copyable types in LLVM 14 to 16)[10], MSVC 32, Java's DualPivotQuicksort 44 (47 through JDK 13), pdqsort 24, Go 12.
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++:

Hoare partition · 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:

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:

Live · Quicksort with different pivots
comparisons
···
max recursion depth
···
vs n log n
···
The bars are the array; the highlighted bar is the current pivot, swaps flash orange and finished pivots turn green. Pick a pivot strategy, an input shape and a size, then press Run. The widget runs a Lomuto-partition quicksort and counts comparisons against the pivot. Try "first element" with "already sorted": the comparisons climb to n(n−1)/2 and the recursion depth to n − 1, the textbook quadratic worst case. Switch to "median-of-three" and the same sorted input splits evenly every time. Then try "organ-pipe" (1, 3, 5, …, max, …, 4, 2) with median-of-three: at n = 96 the depth reaches 28 instead of 6 and the comparison count about a quarter of n(n−1)/2, growing quadratically. That is a bad case for this simple implementation rather than a universal killer; McIlroy showed in 1999 that for essentially any deterministic pivot rule an adversary can build a fully quadratic input[20], which is why production sorts add a fallback.

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:

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.

top-down mergesort · C++
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.

Live · The mergesort recursion tree
levels
···
comparisons
···
aux memory
···
The full array is the top row and each row below splits it in half. Press Run: the leaves appear first, then each merge fills in its parent row, tinting each element by the half it came from. At the default 16 elements the readouts show 4 levels and 16 words of scratch memory. The tree has ⌈log2n⌉ levels; each level merges every element exactly once for O(n) work per level. Total: O(n log n). The aux-memory figure is n because the merge writes to a buffer the size of the active range. In-place merging exists (rotation-based, O(n log² n) overall), and std::stable_sort falls back to it when it can't allocate a buffer, but it is markedly slower. Timsort's merge needs a buffer only as large as the smaller of the two runs, a common compromise.

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.

heapsort with Floyd's heapify · C++
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.

Live · Heapsort step-by-step
phase
···
comparisons
···
swaps
···
The top half is the array and the bottom half the same array drawn as a tree, index 0 at the root. Press Run and watch the build phase sift nodes down, then the extract phase move the root to the growing sorted suffix on the right; the readouts count comparisons and swaps. Phase 1 ("build") starts from index ⌊n/2⌋−1 (the last internal node) and works backward toward the root, sifting each one down. The leaves (half the array) never start a sift-down, and most internal nodes sit near the bottom and sink only a level or two: that is why Floyd's build is O(n). Phase 2 ("extract") swaps the root to the end and re-sifts; each step is one O(log n) sift-down, and this phase does most of the comparisons.

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].

introsort · C++
#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:

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.

Live · Timsort run detection and merge stack
runs found
···
comparisons
···
vs n log n
···
The top half is the array, with each detected run colored (green ascending, orange descending and then reversed), and the bottom half is the merge stack. Pick an input shape and press Run; the readouts give runs found and comparisons. Mostly-sorted input reads 12 runs and 242 comparisons, already-sorted input 1 run and 55. The widget works on 56 elements and skips minrun (real timsort would binary-insertion-sort an array this short in one go) so the natural runs and the merge policy stay visible. "Comparisons" counts the run-detection comparisons plus, for each merge, the combined length of the two runs (an upper bound on the merge's comparisons; galloping is not modeled). On already-sorted input timsort runs in O(n): one run found, no merges. On random input it costs about as much as a plain stable mergesort. Its benefit is on data with existing order: the measurements in listsort.txt show near-linear times on ascending, descending, all-equal, and ascending-with-a-few-changes inputs, where a plain mergesort still pays n log n[11]. The merge stack height is bounded by about logφ(n) ≈ 1.44 log2n when the Fibonacci-style invariant holds; when it doesn't, the stack can outgrow its fixed allocation, which is the 2015 bug below.

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]:

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:

block partition (sketch) · C++
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.

LSD radix sort on uint32 · C++
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));
}

What's intentionally missing

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.

Live · LSD radix sort, byte by byte
passes
···
total ops
···
vs n log n
···
The top row is the array before the current pass and the bottom row after it, colored by the digit this pass sorts on. Press Run, then switch between 4-bit and 8-bit digits; at the default 16 elements and 4-bit digits the readouts show 4 passes and 128 operations. The widget sorts 16-bit keys so each pass stays readable. Digit width is a tunable: more bits per pass means fewer passes but larger histograms, which cost setup time and cache space. 8 bits is the most common choice (Bevy's radsort crate sorts byte by byte), and 11-bit digits, three passes for a 32-bit key, are a well-known alternative; 4 bits is used here so the bucket structure is visible. "Total ops" counts one histogram read and one scatter write per element per pass.

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:

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:

SortTotal workParallel depthIn placeStable
quicksort (serial)O(n log n)O(n log n)yesno
mergesort (serial)O(n log n)O(n log n)noyes
radix sort (serial)O(d·n)O(d·n)auxyes
bitonic sort (parallel)O(n log²n)O(log²n)yesno
GPU radix sortO(d·n)O(d log n)auxyes

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).

Live · The bitonic sort network for n = 8
total ops
···
parallel depth
···
speedup, n/2 threads
···
Each vertical wire is one array position and each layer of arrows one round of compare-and-swaps. Press Run to fire the network a layer at a time; at n = 8 the readouts show 24 operations in 6 layers, a 4.0× speedup with 4 threads. Each layer of the network can run in parallel: every compare-and-swap in a layer touches a disjoint pair of wires. The depth sets the wall time on a parallel machine; the total op count sets the energy spent. With n/2 threads, one per compare-and-swap in a layer, the speedup over running the same network serially is total ops ÷ depth. For n = 4096 the network has 78 layers and about 160,000 compare-and-swaps in total.

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":

Live · Six sorts on identical input
insertion quicksort mergesort heapsort timsort radix
Every racer counts one step per comparison or per element write (a swap is one step, and so is each copy to or from a merge buffer), so the counters compare like with like. Radix finishes first on every shape here, at 4n steps (256 at the default n = 64): the keys are small integers below 256, so two 4-bit passes cover them and it never compares. On already-sorted input insertion sort and timsort tie at n − 1 comparisons. On reverse-sorted input timsort needs only about 1.5n steps (one run, reversed in place: 95 at n = 64) while insertion sort hits its worst case, n(n − 1)/2 comparisons plus as many shifts: 4,032 steps at n = 64. On random input quicksort is the fastest of the comparison sorts. The "mostly sorted" shape swaps n/8 random pairs, which scatters displaced elements across the whole array: at n = 64 insertion sort is still the fastest comparison sort, but by 128 the displacements add up and quicksort pulls ahead. This timsort is simplified (no minrun, no galloping), so it understates the real one on inputs like that.

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:

VP
T
shader id (13b)
material id (16b)
depth (24b)
seq (8b)
render target transparency bit shader id material id depth sequence number

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.

Live · Pack a 64-bit draw-call key
shader binds avoided
···
material binds avoided
···
sort cost (ns/key)
~3
The boxes are sixteen draw calls in sorted order, colored by shader (hue) and material (lightness). Pick a key layout and watch them reorder; the readouts count shader and material binds avoided. The full layout avoids 7 of 16 shader binds and 6 of 16 material binds; the depth-first transparency layout avoids only 2 of each. Higher bits dominate the order. Render target first finishes one pass before the next starts; the transparency bit then separates opaque from transparent draws; shader next keeps pipeline changes down; depth last orders draws front to back within a shader and material. Transparent draws switch to the depth-first, back-to-front layout inside the same key. The stats compare shader and material changes with the worst case of one change per draw. The "sort cost" figure is the ~3 ns per key estimate from §12, not a measurement.

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:

WorkloadRight answerWhy
Generic C++, types with cheap comparestd::sort (introsort / pdqsort)Fast on average, n log n worst case, in place, library-provided.
Generic C++, types with expensive comparea 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 stablestd::stable_sort (a mergesort in libstdc++, libc++, and MSVC)The unstable sorts don't preserve equal-key order.
Real data, often partially sortedtimsort (Python, Java, V8) or powersortAdaptive: O(n) on already-sorted input, and close to linear when the data is a few long runs.
Bounded integer keys, n > 100radix sort (LSD)Linear time, no comparisons, parallelizes well. Common for renderer sort keys.
Small integer range (k no larger than about n)counting sortOne counting pass and one scatter, no comparisons. Java does this for large byte, char, and short arrays.
n < 32, any keysinsertion sortRecursive sorts pay more overhead than the inner-loop work at this scale.
Worst-case latency budget (real-time)heapsort or introsortGuaranteed n log n; quicksort alone can blow the budget on bad input.
Data on GPUbitonic sort or GPU radixBoth 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 RAMexternal mergesortSequential I/O; a k-way merge needs only logk of the run count in passes over the data.
Strings of varied lengthMSD radix or three-way radix quicksortLooks 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:

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:

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

  1. 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.
  2. 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_system time on many_cubes and the regressions on the bevymark and many_sprites benchmarks. Bevy 0.8 shipped radsort for its 3D phase sorts; later releases moved opaque meshes to unsorted bins.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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).
  8. 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 qsort descends from; adopts Tukey's pseudomedian of nine for large arrays and a split-end three-way partition for equal keys.
  9. 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).
  10. LLVM Project. "libcxx std::sort." Implementation in libcxx/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).
  11. 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).
  12. 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.sort for primitive types in Java 7 (JDK-6880672).
  13. 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.
  14. 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_collapse and OpenJDK enlarged its run stack as a result. envisage-project.eu summary.
  15. 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.
  16. 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_unstable from 2017 until Rust 1.81 (2024); ships in Boost.Sort.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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::sort on random integers.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. 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.
  27. 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.
  28. 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.
  29. 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.
  30. 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.
  31. 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.
  32. 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).
  33. Erwin Coumans et al. btAxisSweep3Internal.h, Bullet Physics SDK source. github.com/bulletphysics/bullet3. Incremental sweep-and-prune: sortMinDown, sortMaxUp and friends move each changed endpoint into place in the persistent sorted arrays.
  34. 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.
  35. 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.
  36. 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.

See also