Python sorted() and Timsort: Stability and Multi-Key Sorting

Two reviewers, Asha and Bo, both gave a product two stars. You sort the reviews by rating, and Asha's review still comes before Bo's, exactly as she posted it. That sounds trivially true, yet a perfectly correct sort can break it. Run selection sort on the same data and Bo jumps ahead of Asha. The result is still sorted by rating, so no test on the ratings alone would complain, but anything relying on the earlier order, such as oldest-first within a rating, is silently wrong. The property that protects you is called stability.

Stability: ties keep their input order

A sort is stable if items that compare equal appear in the output in the same relative order as in the input. Merge sort and insertion sort (with a strict comparison) are stable; selection sort and the usual in-place quicksort are not, because they swap items across long distances.

def selection_sort_by_rating(records):
    """Selection sort on (name, rating) pairs, comparing ratings only."""
    a = list(records)
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j][1] < a[smallest][1]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]      # a long-distance swap
    return a


reviews = [("Asha", 2), ("Bo", 2), ("Cyrus", 1)]
print("selection sort:", selection_sort_by_rating(reviews))
print("built-in sort :", sorted(reviews, key=lambda r: r[1]))

selection sort: [('Cyrus', 1), ('Bo', 2), ('Asha', 2)]
built-in sort : [('Cyrus', 1), ('Asha', 2), ('Bo', 2)]

Cyrus had to go to the front, so selection sort swapped him with Asha, which threw Asha behind Bo. Python's built-in sort is guaranteed stable by its documentation, so you can rely on this property rather than hoping for it.

What Timsort does with real data

Python's sorted() and list.sort() use Timsort, a hybrid of merge sort and insertion sort designed around a practical observation: real data is rarely random. It already contains stretches in order, like log files appended chronologically or a list with a few new items on the end. Timsort scans for these natural runs (ascending, or strictly descending, which it reverses), extends very short runs with an insertion-style step, then merges runs. The counter below wraps values in a class that counts every <, which is the only comparison sort uses.

from functools import total_ordering


def scrambled(n, seed=7):
    """Deterministic pseudo-random list without importing random."""
    out, x = [], seed
    for _ in range(n):
        x = (x * 1103515245 + 12345) % 2**31
        out.append(x % 1000)
    return out


@total_ordering
class Counted:
    """Wraps a value and counts every '<' Python asks for. list.sort() only ever uses '<'."""
    comparisons = 0

    def __init__(self, v):
        self.v = v

    def __lt__(self, other):
        Counted.comparisons += 1
        return self.v < other.v

    def __eq__(self, other):
        return self.v == other.v


def cost(values):
    Counted.comparisons = 0
    sorted(Counted(v) for v in values)
    return Counted.comparisons


n = 1000
asc = list(range(n))
desc = asc[::-1]
two_runs = list(range(500, 1000)) + list(range(0, 500))
shuffled = scrambled(n)

print("already sorted     :", cost(asc))
print("strictly descending:", cost(desc))
print("two sorted runs    :", cost(two_runs))
print("scrambled          :", cost(shuffled), "(compare n*log2(n) = 9966)")

already sorted     : 999
strictly descending: 999
two sorted runs    : 1025
scrambled          : 8590 (compare n*log2(n) = 9966)

A sorted list costs 999 comparisons for 1,000 items: one pass to notice that it is a single run, nothing more. A strictly descending list costs the same, because the run is detected and reversed. Two ascending halves cost 1,025, a little more than one comparison per item, because the two runs are merged. Only scrambled data approaches the n log n regime. That is why sorting data that is "mostly sorted" in Python is fast and why appending to a sorted list and re-sorting is not the disaster it looks like.

Sorting by several keys

The key= argument is called once per item to produce the value to compare. Combined with stability, it handles any number of sort criteria. The snippet applies five variants to one support-ticket queue: priority descending then oldest first, the same result by two stable passes, a mixed-direction string sort, ties staying put under reverse=True, and an adapted comparison function.

from functools import cmp_to_key
from operator import itemgetter

tickets = [
    {"id": 101, "priority": 2, "agent": "mira",  "opened": "09:40"},
    {"id": 102, "priority": 1, "agent": "kofi",  "opened": "09:10"},
    {"id": 103, "priority": 2, "agent": "Aiko",  "opened": "08:55"},
    {"id": 104, "priority": 1, "agent": "mira",  "opened": "08:30"},
    {"id": 105, "priority": 3, "agent": "kofi",  "opened": "09:05"},
    {"id": 106, "priority": 2, "agent": "aiko",  "opened": "09:15"},
]


def show(label, rows):
    print(f"{label:34}", [t["id"] for t in rows])


# 1. One tuple key: priority high-to-low (negate), then oldest first
by_tuple = sorted(tickets, key=lambda t: (-t["priority"], t["opened"]))
show("priority desc, opened asc (tuple)", by_tuple)

# 2. Same result with two stable passes: sort by the LEAST important key first
two_pass = sorted(tickets, key=itemgetter("opened"))
two_pass = sorted(two_pass, key=itemgetter("priority"), reverse=True)
show("two stable passes", two_pass)

# 3. Mixed directions on strings cannot be negated: use passes (or cmp_to_key)
by_agent_then_newest = sorted(tickets, key=itemgetter("opened"), reverse=True)
by_agent_then_newest.sort(key=lambda t: t["agent"].casefold())
show("agent asc (caseless), newest first", by_agent_then_newest)

# 4. Ties keep their input order, even with reverse=True
by_priority_only = sorted(tickets, key=itemgetter("priority"), reverse=True)
show("priority desc only (ties stay put)", by_priority_only)


# 5. A comparison function, adapted
def older_first_unless_urgent(a, b):
    if (a["priority"] == 3) != (b["priority"] == 3):
        return -1 if a["priority"] == 3 else 1
    return (a["opened"] > b["opened"]) - (a["opened"] < b["opened"])


show("cmp_to_key (urgent first)", sorted(tickets, key=cmp_to_key(older_first_unless_urgent)))

# sort() returns None
result = [3, 1, 2].sort()
print("list.sort() returns:", result)

priority desc, opened asc (tuple)  [105, 103, 106, 101, 104, 102]
two stable passes                  [105, 103, 106, 101, 104, 102]
agent asc (caseless), newest first [106, 103, 102, 105, 101, 104]
priority desc only (ties stay put) [105, 101, 103, 106, 102, 104]
cmp_to_key (urgent first)          [105, 104, 103, 102, 106, 101]
list.sort() returns: None

• Tuple keys compare element by element, so (-priority, opened) means priority first, then time. Negating works for numbers only.
• Multiple passes exploit stability: sort by the least important key first, then by the most important. Use this for string keys in opposite directions, where negation is impossible. Line 3 in the output sorts agents alphabetically while keeping newest-first order inside each agent, so Aiko's and aiko's tickets (103 and 106) are tied by the caseless key and appear newest first.
• `reverse=True` preserves stability. In line 4 the priority-2 tickets (101, 103, 106) stay in their original order even though the sort is descending. It is not the same as sorting ascending and then reversing the list, which would flip the ties.
• `cmp_to_key` adapts an old-style comparison function. It is the escape hatch for rules that cannot be expressed as a key, and it is slower than a key function.

Common mistakes

• Writing `items = items.sort()`. Symptom: items becomes None and the next line fails with TypeError: 'NoneType' object is not iterable or 'NoneType' object is not subscriptable. sort returns None; use sorted or call sort as a statement.
• Sorting by the wrong key order. Symptom: results grouped by the less important field. With tuple keys the first element wins; with multiple passes the last pass wins.
• Mixed types or missing values in the key. Symptom: TypeError: '<' not supported between instances of ... when a key is None or a string among numbers. Normalise or filter the keys first.
• Comparing dates and numbers as strings. Symptom: "10:05" fine, but "9:40" sorts after "10:05", and "100" sorts before "20". Convert to numbers or zero-padded or ISO formats.
• Using `reverse=True` to "flip" an ascending result and assuming ties flip too. Symptom: ties keep their original order instead of the reverse. If you need exact reversal, reverse the list after sorting.

How this shows up in real projects and interviews

In day-to-day Python the entire sorting decision is usually sorted(..., key=...) with a tuple key, and the lesson from this course is knowing why it behaves as it does: stable, adaptive to existing order, and cheap on nearly sorted data. Leaderboards, report ordering, merging log streams and ordering search results all rely on stability and multi-key sorting. In interviews, expect "is your sort stable and does it matter?", "how would you sort by two fields in opposite directions?" and "how do you sort data that does not fit in memory?". A strong answer names the built-in, explains Timsort in one sentence, and says when you would not use it (huge bounded integer keys, only the top k, data in a database). If you want to practise the surrounding patterns, Arrays and Strings has the problems that use sorted order, and Data Structures covers heaps for top-k.