Sorting: the bound describes the worst case, the library is engineered for the input

Unit eight showed that the answer follows a model. Sorting is the algorithm every interface meets. The lesson usually drawn from it is a single number: comparison sorting cannot beat n log n. The number is true. It is also the least informative thing one can know about the sorts that run.

The claim of this unit is that this bound is a theorem about a stated model, comparison counting, and a stated case, the worst one. The sorts that ship are hybrids engineered for the distributions real data has. Teaching the bound without the engineering misdescribes why a library sort is fast. The bound is model-relative: changing what counts as a step, or what distribution the input has, changes which algorithm is right.

The bound belongs to a model and to the worst case

A comparison sort learns about its input only by comparing keys, and the n log n bound limits how few comparisons can suffice for the hardest input of a given size. It is a statement about the worst case, silent about any particular input. Hoare (1962) introduced quicksort, which partitions an array around a chosen element and sorts the parts, with an expected cost of n log n. Its worst case is quadratic when the pivot is badly chosen (Musser, 1997).

Knuth (1998) shows what a full analysis contains: exact distributions for comparisons and run lengths, external sorting, and the empirical comparisons that drove the algorithms of the 1960s and 1970s.

The input is a variable the worst case ignores

Mannila (1985) defined measures of presortedness and gave algorithms optimal for each, so cost is expressed in the disorder of the instance rather than its size. Estivill-Castro and Wood (1992) survey the resulting field and report that several algorithms already in use are adaptive. One worst-case figure is then a single point in a range.

Shell (1959) beat the obvious quadratic method by comparing elements at a decreasing sequence of gaps, reporting it faster in practice. It reasons about the arrangement of the data, not about an adversary.

Bender, Farach-Colton and Mosteiro (2006) formalise the intuition. Insertion sort run with gaps left between items, as a person leaves gaps in a physical index, has insertion times of O(log n) with high probability. Its total time is O(n log n) with high probability. A procedure taught as quadratic becomes n log n once the arrangement of the data is part of the algorithm. That is why nearly sorted data, what an interface usually holds, is cheap. The list an interface holds is not random: it is the order a person left it in.

What ships is a hybrid, not the textbook algorithm

The sorts in a standard library are not the algorithms in a textbook. Musser (1997) takes up quicksort's quadratic worst case. Earlier repairs that improved the pivot had slowed the average case too much, and heapsort, with an n log n worst case, is on average 2 to 5 times slower than quicksort. He limits the depth of partitioning and switches to heapsort beyond it. That gives a sort as fast as quicksort on average with an n log n worst case, bought by engineering inside the model.

Bentley and McIlroy (1993) redesigned a C library's sort function. They chose partition elements by a sampling scheme and partitioned many equal keys by a way of handling the Dutch National Flag problem. They report it as clearer, faster and more robust than existing sorts. Frazer and McKellar (1970) had shown the direction. Choosing the root of a minimal-storage tree sort from a random sample of the input, instead of assuming a good pivot, improves expected comparisons and approaches the information-theoretic lower bound.

The current engineering is Peters (2021). Pattern-defeating quicksort improves on introsort's heuristics, keeps quicksort's logarithmic memory and fast average case, defeats worst-case patterns deterministically, and runs in linear time on a few common patterns. Its worst case is O(nk) when the input has k distinct values. Not all of this engineering is done by people. Mankowitz and colleagues (2023) cast the design of a sort as a game and trained a deep reinforcement learning agent, AlphaDev, to search instruction sequences; the routines it found for three, four and five elements beat the previous human benchmarks and were integrated into the LLVM standard C++ sort library. Analysis is catching up with what shipped: Collet, Nicaud and Rotondo (2027) show that imposing a minimum run length, as every implementation does, makes Timsort's average-case complexity almost optimal at n log2 n + O(n) comparisons, and that the fixed threshold the languages adopt suffices for realistic input sizes.

The cost model can be changed, and the machine sets the constant

Katajainen and Pasanen (1999) sort an array using O(1) extra space, O(n log n / log log n) element moves and n log2 n + O(n log log n) comparisons. Theirs is the first in-place algorithm to need fewer than n log n moves in the worst case while keeping an n log n comparison bound. Counting moves rather than comparisons, since moving a large record can cost more than comparing it, is a change of cost model that can change the best algorithm.

Edelkamp and Weiss (2019) make the same argument on current hardware. BlockQuicksort compares a block of elements with the pivot and buffers the outcomes, so the partition loop contains no unpredictable branches. They measure more than 80 per cent more elements sorted per second than the C++ standard library sort on random integers, though the standard library wins on sorted or almost sorted inputs.

Contested question: a better algorithm, or engineering inside the bound?

One position holds that the improvement is engineering inside the comparison bound. Musser (1997) and Peters (2021) remove the quadratic worst case without leaving the comparison model, Bentley and McIlroy (1993) reduce the constants, and Katajainen and Pasanen (1999) reduce the moves. A library sort is then a better implementation of a known algorithm, and the bound remains the honest description.

A second position holds that the bound is model-relative, so a different model admits better algorithms. Estivill-Castro and Wood (1992) make cost a function of the instance's disorder, so the bound is one value among many, and Bender and colleagues (2006) turn a quadratic procedure into an n log n one by arranging the data with gaps. Kristo and colleagues (2020) go furthest: their learned sort fits a model of the empirical cumulative distribution of the keys. On up to 1 billion normally distributed doubles they report an average 3.38 times the performance of the C++ standard library sort and 5.54 times a C++ Timsort.

A third position cuts across both. Wild and Nebel (2012) record that Java 7's dual-pivot quicksort was adopted for the runtime library because empirical studies found it faster on average. Earlier theory had judged the dual-pivot idea unpromising. Their first precise average-case analysis explains the surprise, giving 1.9 n ln n minus 2.46 n plus O(ln n) comparisons for a random permutation. The engineering decision came first and the analysis afterwards.

A controlled study would settle the disagreement: fix one set of input distributions, run the hybrid library sorts and the distribution-aware sort on the same data, and record the comparisons, the moves, the cache and branch behaviour and the wall-clock time. The sources here report each algorithm on its own benchmarks, and none runs a distribution-aware sort and a hybrid on the same adversarial and near-sorted inputs, so the question is open. The strongest reading, that the bound can be beaten for data on which only the order of two keys is available, is not supported.

Rate the evidence by kind. Musser (1997), Bentley and McIlroy (1993) and Katajainen and Pasanen (1999) improve a sort without leaving the comparison model, each with a bound or a measurement. Kristo and colleagues (2020) report a fitted model that wins on normally distributed doubles, a case chosen for it rather than a trial on unknown input. The strongest objection is that a distribution-aware sort earns its advantage on the distributions it was fitted to, so the hybrid remains the safer default when the input is unknown. While the dispute is open, a designer records which distributions a chosen sort was tuned for.

Where the argument is heading

The named work points one way: the input distribution is becoming part of the specification. Peters (2021) builds a sort that detects patterns and defeats them. Collet, Nicaud and Rotondo (2027) analyse the minrun heuristic that every implementation ships, and Kristo and colleagues (2020) make a fitted model of the distribution the first step. The bound is not being repealed, and for data on which only the order of two keys is available it cannot be.

The sources this unit rests on

• Bender, M. A., Farach-Colton, M. and Mosteiro, M. A. (2006). Insertion Sort is O(n log n). Theory of Computing Systems. doi:10.1007/s00224-005-1237-z Bender, Farach-Colton and Mosteiro show that insertion sort run with gaps left between items has insertion times of O(log n) and a total time of O(n log n). Gaps explain why nearly sorted data is cheap.
• Bentley, J. L. and McIlroy, M. D. (1993). Engineering a sort function. Software: Practice and Experience. doi:10.1002/spe.4380231105 Bentley and McIlroy recount the redesign of a C library's qsort, which chooses partition elements by a sampling scheme and partitions many equal keys by solving the Dutch National Flag problem. It is the standard account of a shipped sort.
• Collet, N. A., Nicaud, C. and Rotondo, P. (2027). On the average complexity of Timsort with the minrun heuristic. Information Processing Letters 195. doi:10.1016/j.ipl.2026.106665 Collet, Nicaud and Rotondo establish that imposing a minimum run length, as every Timsort implementation does, makes its average-case complexity almost optimal at n log2 n comparisons. It is a recent analysis of a sort adopted long before it was analysed.
• Edelkamp, S. and Weiss, A. (2019). BlockQuicksort: how branch mispredictions don't affect quicksort. ACM Journal of Experimental Algorithmics. doi:10.1145/3274660 Edelkamp and Weiss give BlockQuicksort, which compares a block of elements with the pivot and buffers the outcomes so the partition loop has no unpredictable branches, and measure more than 80 per cent more elements sorted per second than the C++ standard library sort.
• Estivill-Castro, V. and Wood, D. (1992). A survey of adaptive sorting algorithms. ACM Computing Surveys. doi:10.1145/146370.146381 Estivill-Castro and Wood survey adaptive sorting, defining a sort's complexity in terms of the disorder of the given instance rather than only its size, and catalogue measures of presortedness with algorithms optimal for each.
• Frazer, W. D. and McKellar, A. C. (1970). Samplesort: A Sampling Approach to Minimal Storage Tree Sorting. Journal of the ACM. doi:10.1145/321592.321600 Frazer and McKellar choose the root of a minimal-storage tree sort from a random sample taken as the input is read, improving expected comparisons and approaching the information-theoretic lower bound. It is the ancestor of modern pivot sampling.
• Hoare, C. A. R. (1962). Quicksort. The Computer Journal. doi:10.1093/comjnl/5.1.10 Hoare introduces quicksort, partitioning an array around a chosen element and sorting the parts, with an expected cost of n log n, and notes the quadratic worst case from a badly chosen pivot. It is the origin of the sort most libraries build on.
• Katajainen, J. and Pasanen, T. A. (1999). In-place sorting with fewer moves. Information Processing Letters. doi:10.1016/s0020-0190(99)00038-1 Katajainen and Pasanen sort in place using O(1) extra space, O(n log n / log log n) moves and n log2 n comparisons, the first in-place method to need fewer than n log n moves.
• Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley. https://archive.org/details/B-001-001-250-NLA Knuth's third volume derives exact distributions for comparison sorts and run lengths, external sorting and the empirical comparisons of the 1960s and 1970s. It is a reference work that shows what a full analysis contains.
• Kristo, A., Vaidya, K., Cetintemel, U., Misra, S. and Kraska, T. (2020). The Case for a Learned Sorting Algorithm. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. doi:10.1145/3318464.3389752 Kristo, Vaidya, Cetintemel, Misra and Kraska fit a model of the empirical cumulative distribution of the keys, place each key near its final position and refine locally, reporting an average 3.38 times the performance of the C++ standard library sort. It is a case chosen for the model rather than a general trial.
• Mannila, H. (1985). Measures of Presortedness and Optimal Sorting Algorithms. IEEE Transactions on Computers. doi:10.1109/tc.1985.5009382 Mannila defines measures of presortedness and gives sorting algorithms optimal with respect to each, so a sort's cost is expressed in how disordered the instance is. It is the primary paper behind adaptive sorting.
• Mankowitz, D. J., Michi, A., Zhernov, A. and colleagues (2023). Faster sorting algorithms discovered using deep reinforcement learning. Nature. doi:10.1038/s41586-023-06004-9 Mankowitz and colleagues cast the design of a sort routine as a game and train AlphaDev to search instruction sequences, discovering routines for three to five elements faster than the known benchmarks, which were integrated into the LLVM C++ sort library.
• Musser, D. R. (1997). Introspective Sorting and Selection Algorithms. Software: Practice and Experience. doi:10.1002/(sici)1097-024x(199708)27:8<983::aid-spe117>3.0.co;2-# Musser limits the depth of partitioning and switches to heapsort past that limit, since heapsort has an n log n worst case but is on average 2 to 5 times slower than quicksort. It is the standard repair inside the comparison model.
• Peters, O. R. L. (2021). Pattern-defeating quicksort. arXiv. https://arxiv.org/abs/2106.05123 Peters gives pattern-defeating quicksort, which improves on introsort's heuristics, keeps quicksort's logarithmic memory and fast average case, defeats worst-case patterns deterministically, and runs in linear time on a few common patterns. It is an arXiv preprint.
• Shell, D. L. (1959). A high-speed sorting procedure. Communications of the ACM. doi:10.1145/368370.368387 Shell compares elements at a decreasing sequence of gaps, moving elements a long way in each pass, and reports it faster than the earlier quadratic methods. It is the first schedule here that beats the obvious method.
• Wild, S. and Nebel, M. E. (2012). Average Case Analysis of Java 7's Dual Pivot Quicksort. Lecture Notes in Computer Science. doi:10.1007/978-3-642-33090-2_71 Wild and Nebel give the first precise average-case analysis of the dual-pivot quicksort adopted for Java 7, chosen on empirical studies, deriving 1.9 n ln n minus 2.46 n comparisons. It answered a decision taken on measurements alone.