Sorting Algorithms

01Why a sort, not a stopwatch

The frame budget at 60 fps is 16.67 ms. 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]. 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 L1, 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.

This tutorial 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

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). Above 1,000 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]. Sorting on stored-program computers starts with von Neumann in 1945, and the research is still active. The dates that matter for engine work:

Two patterns hold across the timeline. 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.

03Why comparison sorts can't beat n log n

Before building any sort, it helps to know the floor. Any algorithm that sorts by comparing pairs of elements (no peeking at their bits, no precomputed table) must do about n log₂ 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 log₂ L. So the height (the worst-case number of comparisons on some input) is at least log₂(n!).

The middle step uses a Stirling-type bound: n! > (n/e)ⁿ for n ≥ 1. The subtracted term n log₂(e) ≈ 1.443 n is lower order and disappears into the Ω. The conclusion: any sort that uses only pairwise comparisons does at least n log₂ n − 1.443 n comparisons on some input^[18]. 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 ⌈log₂(6)⌉ = 3 comparisons. Click a permutation to highlight the path:

04Insertion sort, the small-n champion

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.

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:

05Quicksort: partition, recurse, pray

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

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

Mergesort is 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 log₂n 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);
}

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 2³⁰ 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.

07Heapsort, the worst-case insurance policy

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.

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

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 log₂n, 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.
}

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 log₂n?

The constant in front of the log is a tradeoff. A perfectly balanced quicksort recurses exactly log₂n 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 ⌊log₂n⌋; libstdc++ and libc++ use it, and MSVC allows about 1.5 log₂n.

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

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.

The 2015 invariant bug

Stijn de Gouw and colleagues at CWI Amsterdam, working in the KeY verification tool 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

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::sort on 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 log₂ 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^[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.

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

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.

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.

12Radix sort: linear time, no comparisons

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. MSD radix sort is the variant for strings and variable-length 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));
}

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

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.

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

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 log₂ 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:

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

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:

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

The decision table for "which sort do I reach for":

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

Sort bugs that turn up in production code:

• Non-strict weak ordering. std::sort requires 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::sort is allowed to reorder equal elements; std::stable_sort is 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::sort takes 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; 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 2³⁰ 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->material against b->material dereferences 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

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_sort is typically heap-based (O(n log k)); when k is a large fraction of n, std::nth_element followed 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) · log_M/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

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 ⌊log₂n⌋ 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 log₂n 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 2³⁰ 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 ⌈log₂ 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) · log_M/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.