Sorting Algorithms in the Real World

list.sort() and sorted() both run Tim Sort, designed by Tim Peters for Python 2.3 in 2002. It scans the array for "runs" of already-ordered elements, extends short runs to a minimum length using Insertion Sort, then merges the runs with a tuned Merge Sort.

Two decisions drove it. First, stability was made a language guarantee, not an implementation detail — which rules out Quick Sort and Heap Sort entirely. Second, Peters observed that real-world lists are rarely uniformly random: they are logs with a few late arrivals, records already grouped by one field, data that was sorted before someone appended to it. Tim Sort is built to exploit exactly that, so it approaches O(n) on such input where a textbook sort would spend the full O(n log n).

The guarantee is what makes the common Python idiom work: sort by the secondary key, then sort by the primary key, and the secondary ordering survives inside each group.

Java is the clearest illustration that the right answer depends on the data. Arrays.sort() does two completely different things depending on what you pass it.

For objects, it runs Tim Sort. Objects have identity: two records can compare equal while being distinguishable, so scrambling their order would be a visible bug. Stability is required, and Java's specification says so explicitly.

For primitives — int[], double[] — it runs dual-pivot Quick Sort (Vladimir Yaroslavskiy, 2009). Here stability is meaningless: two equal ints are not merely equal, they are indistinguishable, so no observable ordering can be disturbed. With that constraint removed, Java is free to pick the faster in-place algorithm. Dual-pivot partitions into three regions rather than two, which reduces both comparisons and cache misses relative to classic single-pivot Quick Sort.

This is worth internalising: Java did not decide which algorithm is better. It decided that the question depends on whether equality is observable.

std::sort runs Introsort, and the C++ standard requires O(n log n) worst case — which plain Quick Sort cannot promise. Introsort satisfies both goals at once:

• Begin as Quick Sort, for its speed and cache behaviour.
• Track recursion depth. If it exceeds roughly 2·log n, the pivots are clearly going badly, so switch that sub-problem to Heap Sort — slower, but O(n log n) guaranteed.
• For partitions below a small threshold (about 16 elements), stop recursing and finish with Insertion Sort.

Note that std::sort is explicitly not stable; C++ offers std::stable_sort separately, which uses a merge-based algorithm and will allocate memory to do it. The standard library makes you choose, rather than paying for stability you may not need.

The depth-limit trick is the generalisable idea here: you do not need to predict the bad case in advance, you just need to detect that you are in it and change strategy.

Array.prototype.sort() has the most interesting history. For most of JavaScript's life the specification did not require stability, and engines differed: V8 used an unstable Quick Sort for larger arrays and Insertion Sort for small ones, so the same code could produce different orderings in different browsers, and even for different array lengths in the same browser.

V8 7.0 (Chrome 70, 2018) switched to Tim Sort, and ECMAScript 2019 made stability mandatory. Every current engine is now stable.

The other quirk remains, and it catches beginners constantly: with no comparator, sort() converts elements to strings. So [10, 9, 1].sort() yields [1, 10, 9], because "10" sorts before "9" the way ten comes before nine in a dictionary. Always pass a comparator for numbers: arr.sort((a, b) => a - b). More in sorting algorithms in JavaScript.

When PostgreSQL executes an ORDER BY that cannot be satisfied from an index, it first tries to sort in memory using a quicksort variant. If the data exceeds the work_mem budget, it switches to an external merge sort: sort what fits into a "run", write that run to a temporary file, repeat, then merge the runs.

Merge Sort is the right algorithm here for a reason that has nothing to do with Big O. Merging reads each run sequentially, and sequential access is what storage hardware is good at — even on SSDs, and dramatically so on spinning disks. Quick Sort's partitioning jumps back and forth across the data, which is nearly free in RAM and ruinous on disk.

The same structure appears in every large-scale data system: the shuffle-and-sort phase of MapReduce, Spark's sort-based shuffle, and the compaction step in log-structured merge trees such as those inside Cassandra and RocksDB are all merges of sorted runs.

On a GPU the ranking inverts. Quick Sort is a poor fit: it is recursive, its work is unbalanced between branches, and thousands of threads executing different branches of the same instruction stream stall each other. Radix Sort is close to ideal: fixed number of passes, no data-dependent branching, and each pass is a counting-and-scatter operation that maps directly onto massively parallel hardware. It is what NVIDIA's CUB and Thrust libraries use, and it routinely outruns comparison sorts by a wide margin on GPU.

The lesson is that "fastest" is a property of the algorithm and the machine. Radix Sort did not get better; the hardware changed, and the hardware rewards predictability over cleverness.

Six platforms, and the same handful of reasons keep deciding the outcome:

• Stability is a product decision, not a performance one. Where equality is observable (objects, records, user-facing lists), stability is required and the algorithm choice follows from it. Where it is not (primitives), the faster in-place option wins.
• Real data is not random. Tim Sort's dominance is entirely down to exploiting pre-existing order, which textbook average-case analysis assumes away.
• Detect the bad case instead of predicting it. Introsort's depth counter and PostgreSQL's spill-to-disk check are the same idea: a cheap runtime test that switches strategy.
• Memory hierarchy beats operation counts. Cache locality decides Quick Sort vs Merge Sort in RAM; sequential access decides it on disk; branch predictability decides it on GPU. See why Quick Sort is faster in practice.
• Small inputs get their own algorithm. Every hybrid here falls back to Insertion Sort below some threshold, because asymptotic advantages do not exist at n = 12.

If you want to see the first four of those with your own eyes, run the same array through Quick Sort and Merge Sort in the visualiser, then run Insertion Sort on an already-sorted array and watch it finish almost immediately.