Timsort, Stability & sorted()

In production Python you will almost never implement a sorting algorithm. You will call sorted() or list.sort(). That is the right call. But knowing what runs underneath — and what stability means — is what separates someone who gets bitten by subtle data bugs from someone who does not.

Timsort: the algorithm you are already using

Both sorted() and list.sort() use Timsort, a hybrid algorithm designed by Tim Peters in 2002 specifically for the kinds of data real programs produce.

The idea in one paragraph: Timsort scans the input for already-sorted subsequences called runs. If a run is short, it extends it using insertion sort (which is fast on small or nearly-sorted data). It then merges those runs using merge sort’s merge step. The result is an algorithm that is:

• O(n log n) worst case — the same guarantee as merge sort.
• ~O(n) on already- or nearly-sorted data — because it finds one big run and does almost no merging.

Real-world data is rarely a random shuffle. Logs are nearly time-ordered. A re-sorted leaderboard changes only a few positions. Timsort exploits that structure without you doing anything special.

# Both of these are Timsort — in-place vs returning a new list
scores = [88, 72, 95, 61, 72, 88]

ascending = sorted(scores)       # returns a new list; original unchanged
scores.sort()                    # sorts in place; returns None

# Nearly-sorted — Timsort will detect the existing run and be very fast
almost_sorted = list(range(10_000)) + [10001, 9998, 10000]
almost_sorted.sort()

Stability — what it means and why it matters

A sort is stable if two elements that compare as equal keep their original relative order after sorting. Timsort is stable. This is not an accident; it was a deliberate design requirement.

Why does this matter? Consider a leaderboard with tied scores:

# Input order: Alice appears before Bob, both have score 72
players = [("Alice", 72), ("Carol", 95), ("Bob", 72), ("Dave", 61)]

by_score = sorted(players, key=lambda p: p[1])
# [('Dave', 61), ('Alice', 72), ('Bob', 72), ('Carol', 95)]
#                  ^^^^^^^^^^^  ^^^^^^^^^^
#                  Alice before Bob — input order preserved among ties

Alice appeared before Bob in the input, so she appears before Bob in the output. With an unstable sort that guarantee disappears. That might seem minor until you are building a ranking system where tie-breaking order carries meaning.

The two-pass multi-key trick

Stability is what makes the following pattern possible and correct. To sort by a primary key, then by a secondary key as a tiebreaker:

1. Sort by the secondary key first.
2. Stable-sort by the primary key.

Because the second sort is stable, equal primary-key elements retain the order they got in step 1 — which was sorted by secondary key.

This is also how you can replicate multi-key sorting anywhere stability is guaranteed — and it is why stability is a prerequisite for the pattern to be correct. (pandas sort_values(by=["dept", "salary"]) achieves the same result in a single pass using a composite sort key, but the two-pass trick is the pattern to reach for when you need different sort directions per field.)

Run the playground below to see both ideas at once.

key=, reverse=, and why key= beats a comparator

sorted() and list.sort() both accept two optional arguments you will use constantly.

key= takes a callable. Python calls it once per element, stores the result, and sorts by those stored values. The original elements are carried along for the ride. This is the classic decorate-sort-undecorate pattern (also called the Schwartzian transform):

# Sort words by length, then alphabetically within same length
words = ["fig", "apple", "banana", "kiwi", "date"]

# key= is called once per word — O(n) key computations, then O(n log n) comparisons
by_length = sorted(words, key=lambda w: (len(w), w))
print(by_length)
# ['fig', 'date', 'kiwi', 'apple', 'banana']

The alternative — a custom cmp function — was removed in Python 3 because it is strictly worse: a cmp function is called O(n log n) times during sorting, whereas key= computes values just n times up front. For expensive keys (database lookups, regex matches, model inference scores) this difference is significant.

functools.cmp_to_key exists as an escape hatch for cases where a pairwise comparison is truly unavoidable, but those cases are rare.

reverse=True sorts descending without the cost of reversing the list afterward:

# Top-5 scorers
top5 = sorted(players, key=lambda p: p[1], reverse=True)[:5]

You can also negate a numeric key (key=lambda p: -p[1]) for descending order when you need descending on one field and ascending on another in the same pass — though the two-pass approach above is usually clearer.

Quick check