Overview
A sort's stability guarantee, whether elements comparing as equal keep their original relative order, is what makes sorting by multiple keys in separate passes actually correct: sort by the secondary key, then stably sort by the primary key, and equal-primary-key elements retain their secondary-key order from the first pass automatically. Python's built-in sort is both guaranteed stable and implemented as Timsort, which specifically detects and merges already-ordered runs already present in the input rather than treating every input as uniformly random, giving it O(n) on the best case (already-sorted input) instead of the flat O(n log n) a textbook mergesort always pays. Real-world data is very often partially sorted already, which is exactly the case Timsort is built to exploit, and it still special-cases small subarrays with simple insertion sort internally, since a lower-constant-factor O(n^2) approach genuinely wins at small sizes despite losing asymptotically.
Quick Reference
| Property | What it means |
|---|---|
| Stable sort | Equal-key elements keep their original relative order |
| Timsort best case | O(n) - exploits existing sorted runs |
| Timsort average/worst case | O(n log n) |
| Multi-key sort via stability | Sort by secondary key, then stably sort by primary key |
Syntax
# Stability lets you sort by multiple keys in separate passes.
by_age = sorted(students, key=lambda s: s.age)
by_grade_then_age = sorted(by_age, key=lambda s: s.grade)Examples
data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
sorted(data, key=lambda x: x[0])
# [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
# 'blue' entries keep their original relative order - stabilitySort by secondary key first, then primary key, when keys are separate passes
Because the sort is stable, sorting by the secondary key first and then stably sorting by the primary key produces a correct combined sort, equal-primary-key elements keep their secondary-key order automatically. This only works because of the stability guarantee.
Visual Diagram
Common Mistakes
- Assuming a general "sort" function is unstable and writing a single combined comparator for multi-key sorts, when a stable sort's simpler sequential-pass approach would work and be easier to reason about.
- Assuming every sort is O(n log n) uniformly, missing that real implementations like Timsort adapt to already-ordered input for a much better best case.
- Choosing a textbook O(n log n) algorithm for consistently small inputs, when a simpler O(n^2) approach would actually run faster due to lower constant factors.
- Forgetting that stability is a guarantee the algorithm has to provide explicitly; not every general sorting algorithm (heapsort, for instance) is stable by default.
Performance
- Timsort's best case (already or nearly sorted input) is O(n), a genuine, exploitable advantage over algorithms with a flat O(n log n) regardless of input order.
- Small-subarray special-casing (falling back to insertion sort) is a real, deliberate optimization in production sort implementations, not an oversight, because constant factors dominate at small n.
Best Practices
- Rely on stability for multi-key sorts done as sequential single-key passes, rather than writing one more complex combined comparator.
- Don't assume O(n log n) is the only relevant number, check whether the actual data is likely to already be partially ordered, which real sort implementations exploit.
- Trust a language's built-in general-purpose sort for typical use, it's very likely already tuned (stability, run detection, small-input special-casing) beyond what a hand-rolled implementation would bother with.
- Verify a specific sort's stability guarantee explicitly before relying on it, rather than assuming all sorting algorithms provide it.