Quick Sort vs Tim Sort

Quick Sort is often fastest on uniformly random arrays, but it is unstable and has an O(n²) worst case. Tim Sort is stable, guarantees O(n log n), and reaches O(n) on partially-sorted data by detecting runs. Since real inputs are frequently partially ordered, Tim Sort often matches or beats Quick Sort on practical workloads.

A general-purpose library sort must behave predictably for everyone. Stability enables correct multi-key sorting, which countless applications depend on. Quick Sort cannot offer stability without giving up its in-place advantage, so language designers chose Tim Sort (for objects) and reserved Quick Sort variants for primitives where stability does not matter.

For a custom hot loop on random primitive data, Quick Sort or Introsort may be faster. For a default that must be stable and robust on real data, Tim Sort wins — which is why it is everywhere. See what algorithm Python uses for the full story.

If Quick Sort is faster on random data, it is worth asking why Python, Java (for objects), Swift and Android all made Tim Sort their default instead. Three reasons, and none of them is raw speed.

Real data is not random. This is the central bet Tim Sort makes. Production data is very often partially ordered already — records appended to a sorted table, log entries mostly in timestamp order, a list being re-sorted after a few edits. Tim Sort detects those existing runs and skips redoing them, approaching O(n) on such input. Quick Sort is indifferent to existing order and does the same work regardless. On the data libraries actually see, Tim Sort's adaptivity frequently outweighs Quick Sort's tighter inner loop.

Stability is not optional for objects. A library sorting arbitrary objects cannot know whether the caller depends on equal elements keeping their order — and the multi-pass sorting idiom (sort by name, then by department) breaks silently without it. A default sort that is unstable is a default sort that produces subtly wrong results for a whole category of legitimate use. Quick Sort cannot offer stability without giving up the in-place property that makes it fast.

Predictability beats peak speed. Tim Sort is O(n log n) in the worst case, full stop. Quick Sort's worst case is O(n²), and while randomised pivots make that vanishingly unlikely, "vanishingly unlikely" is a harder promise for a standard library to make than "never". Library authors generally prefer a slightly slower algorithm with no bad tail over a slightly faster one with a catastrophic one.

Note that this is not a contradiction of Quick Sort being the right choice elsewhere. The same standard libraries still use dual-pivot Quick Sort for primitive arrays, precisely because stability is meaningless for primitives and so Quick Sort's one real drawback costs nothing there. Java making opposite choices for int[] and Integer[] is the clearest illustration of the trade-off in the whole language.