Stability, in-place, and choosing a sort

Beyond complexity, three properties decide which sort fits.

Stable — equal elements keep their original relative order.
In-place — O(1) or O(log n) extra memory.
Adaptive — faster on partly sorted input.

Why stability matters

Sort employees by name, then by department. With a stable sort, people stay alphabetical within each department. With an unstable one, that first sort is destroyed. Multi-key sorting by repeated passes only works if each pass is stable.

What real libraries use

Timsort — a merge sort that finds already-sorted runs and extends them with insertion sort — is the default in Python and Java (for objects) and in V8's Array.prototype.sort. On real data, which is full of partially ordered stretches, it approaches O(n). On random data it is a solid O(n log n), and it is stable.

Since ES2019, JavaScript's sort is required to be stable. Older engines were not, and code written against them may still carry workarounds.

The comparator trap

[10, 9, 1].sort();                    // [1, 10, 9] — string comparison!
[10, 9, 1].sort((a, b) => a - b);     // [1, 9, 10]

The default comparator converts to strings. This is one of the most-hit bugs in JavaScript, and it is silent — the output is sorted, just not numerically.

Your comparator must be consistent: return negative, zero, or positive, and never depend on anything mutable. An inconsistent comparator can make an optimised sort throw, or produce garbage.

Beating O(n log n)

Comparison sorts cannot do better than O(n log n) — there are n! possible orderings and each comparison eliminates at most half. But when you know the shape of the keys, you can avoid comparing:

• Counting sort — O(n + k) for small integer ranges.
• Radix sort — O(d × n) for fixed-width keys, digit by digit.
• Bucket sort — O(n) for values spread evenly over a known range.

They are not general-purpose, and that is the point: the extra knowledge is what buys the speed.