Card 05/ 08
Built-In Sorts in Python, Java and TypeScript
Python and TypeScript use a stable merge-based sort for everything; Java sorts primitives with an unstable quicksort.
The built-in sorts of Python, Java and TypeScript are all O(n log n) in the worst case and all tuned far beyond a textbook version, but they differ in which algorithm they run, whether equal items keep their order, and what order they sort into when you pass nothing. This card compares them on those points and gives the rule for using each.
Most of them descend from Timsort, which Tim Peters wrote for Python in 2002. Timsort is a merge sort that first scans the input for runs, stretches already in order, extends short runs with binary insertion sort, and then merges the runs. Input that is nearly sorted contains a few long runs, so Timsort is adaptive: it sorts such input in close to n comparisons, and it is stable because a merge takes from the left run on a tie.
| Language | Call | Algorithm family | Stable | Order with no comparator | Version |
|---|---|---|---|---|---|
| Python | list.sort(), sorted() | Timsort with the powersort merge policy; binary insertion sort below 64 items | Yes | By < on the items | CPython 3.14 |
| Java, objects | Arrays.sort(Object[]), List.sort, Collections.sort | TimSort, an adaptive merge sort | Yes, required by the documentation | Natural order, compareTo | JDK 25 |
| Java, primitives | Arrays.sort(int[]) and the other primitive types | Dual-pivot quicksort, falling back to heapsort past a recursion depth limit | No, though equal primitives cannot be told apart | Numeric | JDK 25 |
| TypeScript | Array.prototype.sort, toSorted | Timsort in V8, the engine behind Node and Chrome, since V8 7.0 | Yes, required since ES2019 | By each value converted to a string | Node 24 |
The three agree on the common case: sorting objects by a key is stable and O(n log n) in every language. CPython's notes on its sort, Objects/listsort.txt, describe the run detection, the 64-item threshold and the powersort merge policy it has used since Python 3.11. Java's documentation for Arrays.sort(Object[]) calls it a stable, adaptive, iterative mergesort adapted from Python's, needing up to n/2 extra references.
They differ in two places. Java sorts primitive arrays with a dual-pivot quicksort, by Vladimir Yaroslavskiy, Jon Bentley and Joshua Bloch, which is unstable and needs no merge buffer; stability cannot matter there, because two equal int values are indistinguishable. And TypeScript's default order is not numeric: called with no comparator, sort converts every value to a string and compares the strings, which Sorting Numbers in TypeScript Without a Comparator shows going wrong.
Use the built-in sort unless a constraint from Choosing a Sort by Memory, Stability and Worst Case rules it out. In Python, pass a key function. In Java, sort objects when equal keys must keep their order, since a primitive array cannot carry the rest of a record anyway. In TypeScript, always pass a comparator unless the values are strings.
← → move through sections and cards