Timsort, Stability & sorted()

In real Python you will almost never write a sorting algorithm. You will call sorted() or list.sort(), and that is the right call.

But knowing what runs underneath those calls — and what the word stable means — is exactly what separates someone who quietly gets bitten by a data bug from someone who sees it coming. So let us look under the hood, just enough.

Timsort: the sort you are already using

Both sorted() and list.sort() use Timsort, a hybrid that Tim Peters designed in 2002 for the kind of data real programs actually produce.

The idea fits in a breath. Timsort scans the input for stretches that are already in order, called runs. Short runs it extends with insertion sort, which is fast on small or nearly-ordered data. Then it stitches the runs together with merge sort’s merge step. The result inherits the best of both: an O(n log n) worst case like merge sort, but close to O(n) when the data is already nearly sorted, because then there is one long run and almost nothing to merge.

And real data is rarely a true shuffle. Logs arrive nearly in time order; a re-sorted leaderboard moves only a few rows. Timsort exploits that structure for free — you do nothing special to get it.

scores = [88, 72, 95, 61, 72, 88]
ascending = sorted(scores)   # returns a new list, original untouched
scores.sort()                # sorts in place, returns None

Stability — and why it earns its keep

A sort is stable if two elements that compare as equal come out in the same order they went in. Timsort is stable, and that was a deliberate design requirement, not a happy accident.

Why care? Picture a leaderboard with tied scores. Alice and Bob both scored 72, and Alice came first in the input.

players = [
    ("Alice", 72),
    ("Carol", 95),
    ("Bob",   72),
    ("Dave",  61),
    ("Eve",   61),
]

by_score = sorted(players, key=lambda p: p[1])
for name, score in by_score:
    print(name, score)

Dave 61
Eve 61
Alice 72
Bob 72
Carol 95

Dave came before Eve in the input, and Alice before Bob, and the stable sort keeps it that way among the ties. That guarantee looks small until you are building a ranking where the tie-break order carries real meaning.

The two-pass multi-key trick

Stability is what makes this pattern correct. To sort by a primary key and break ties with a secondary key, you sort twice, secondary first:

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

Because the second sort is stable, rows with an equal primary key keep the order the first pass gave them — which was the secondary key.

# Goal: score descending, and name ascending among ties
step1 = sorted(players, key=lambda p: p[0])               # secondary: name
step2 = sorted(step1, key=lambda p: p[1], reverse=True)   # primary: score (stable)
for name, score in step2:
    print(name, score)

Carol 95
Alice 72
Bob 72
Dave 61
Eve 61

Among the 72s, Alice comes before Bob; among the 61s, Dave before Eve — each tie broken by name, exactly as asked. (pandas does the same with sort_values(by=[...]) and a list of directions, but the two-pass trick is the one to reach for in plain Python when fields need different directions.)

key=, reverse=, and why key= wins

Both sorted() and list.sort() take two arguments you will use constantly.

key= takes a function. Python calls it once per element, remembers the result, and sorts by those remembered values — carrying the original elements along. That once-per-element promise is the whole point:

words = ["fig", "apple", "banana", "kiwi", "date"]
print(sorted(words, key=lambda w: (len(w), w)))   # by length, then alphabetically

['fig', 'date', 'kiwi', 'apple', 'banana']

The old alternative — a pairwise comparison function — was removed in Python 3 because it is strictly worse: a comparator is called O(n log n) times during the sort, whereas key= runs just n times up front. When the key is expensive (a database lookup, a regex, a model score), that difference is enormous. functools.cmp_to_key survives as an escape hatch for the rare case where only a pairwise comparison will do.

reverse=True sorts descending without the cost of reversing afterward — sorted(players, key=lambda p: p[1], reverse=True)[:5] gives you the top five in one line.

Practice