Python’s Built-in Sort (Timsort)

Every time you call sorted() or list.sort() in Python, you are running Timsort — a hybrid sorting algorithm invented by Tim Peters in 2002 specifically for CPython. It is not a textbook algorithm you would normally implement by hand, but understanding how it works matters: it explains why Python’s sort is fast on real-world data, why it is stable, and why certain sorting patterns (like sorting by multiple keys) work the way they do. This lesson covers Timsort from the outside (the API you actually call) and the inside (the merge/insertion hybrid that makes it efficient).

Overview / How it works

Timsort is a hybrid of insertion sort and merge sort, designed around one key observation: real-world data is rarely random. Log files, timestamps, partially-edited lists, and concatenated sorted chunks all tend to contain long stretches that are already in order. A generic merge sort ignores this and always does the same O(n log n) work. Timsort detects and exploits existing order, so it can finish in O(n) time on data that is already sorted or nearly sorted, while still guaranteeing O(n log n) in the worst case.

Here is the intuition with a concrete scenario. Suppose you have a list of 10,000 numbers that were built by appending three separately-sorted batches of results together. Timsort scans left to right and finds runs: maximal stretches that are already non-decreasing (or strictly decreasing, which it reverses in place to make ascending). If a run it finds is shorter than a computed minimum length (minrun, typically between 32 and 64 depending on list size), it extends that run using binary insertion sort — insertion sort is fast on small, nearly-sorted chunks because each element usually needs only a few shifts. For lists shorter than 64 elements, the minrun calculation ends up covering the whole list, so Timsort effectively just performs one binary insertion sort pass on small lists.

Once runs of at least minrun length exist, Timsort merges them the way merge sort does — but it merges intelligently. It keeps a stack of pending runs and only merges adjacent runs when their lengths satisfy certain balance invariants, which keeps merges roughly equal in size (avoiding the worst-case O(n2) behavior of naively merging a tiny run into a huge one repeatedly). It also uses a technique called galloping mode: if one run keeps "winning" comparisons against the other during a merge (meaning one run’s elements are consistently smaller), Timsort switches to a binary-search-based mode that skips ahead in large jumps instead of comparing one element at a time.

You interact with Timsort through two entry points. sorted(iterable, key=None, reverse=False) accepts any iterable and returns a new sorted list, leaving the original untouched. list.sort(key=None, reverse=False) only works on lists, sorts in place, and returns None. Both accept a key function, which is called exactly once per element up front (an approach sometimes called "decorate-sort-undecorate" or the Schwartzian transform) — the results are cached, so an expensive key function does not get recomputed on every comparison. Python 3 removed the old cmp comparator parameter entirely; key is the only supported customization.

Time and Space Complexity

Timsort’s complexity depends heavily on how much existing order is in the input, which is exactly the property it was designed to exploit.

Case Time Why
Best case O(n) Input is already sorted (or made of a few long sorted/reverse-sorted runs). Timsort detects the run(s) in a single linear scan and needs only cheap merges to combine them, with no need for the log n merge passes that a naive merge sort always performs.
Average case O(n log n) Typical unordered data breaks into many short runs. Extending each to minrun costs roughly O(n) total, and merging n / minrun runs pairwise costs O(n log n), matching classic merge sort.
Worst case O(n log n) Even adversarial input (e.g., data designed to defeat galloping mode) is bounded by the same merge structure as merge sort — Timsort never degrades to O(n2), unlike quicksort’s worst case.
Space O(n) Merging is not fully in-place; Timsort allocates a temporary buffer (up to about half the list) to merge runs, and its internal run-length bookkeeping stack adds negligible O(log n) extra.

An important extra property that complexity numbers alone do not capture: Timsort is stable. If two elements compare equal under the sort key, their original relative order is preserved. This matters for multi-key sorting: sort by a secondary key first, then by a primary key, and equal-primary-key groups will still be internally ordered by the secondary key.

Examples

The first example contrasts the two entry points — sorted(), which returns a new list, and list.sort(), which mutates in place and returns None.

def demonstrate_sort_vs_sorted() -> None:
    numbers = [5, 2, 9, 1, 5, 6]
    sorted_copy = sorted(numbers)
    print('Original:', numbers)
    print('Sorted copy:', sorted_copy)

    numbers.sort()
    print('After in-place sort:', numbers)


demonstrate_sort_vs_sorted()

Output:

Original: [5, 2, 9, 1, 5, 6]
Sorted copy: [1, 2, 5, 5, 6, 9]
After in-place sort: [1, 2, 5, 5, 6, 9]

sorted(numbers) builds a brand-new list, so the line right after it still prints the untouched original. Only after calling numbers.sort() does the original variable itself become sorted.

The second example shows the key parameter, which is how you customize what "sorted" means without writing a comparator.

def sort_words_by_length(words: list[str]) -> list[str]:
    return sorted(words, key=len)


words = ['banana', 'kiwi', 'fig', 'apple', 'date']
by_length = sort_words_by_length(words)
print('By length:', by_length)

by_length_desc = sorted(words, key=len, reverse=True)
print('By length descending:', by_length_desc)

by_alpha = sorted(words)
print('Alphabetical:', by_alpha)

Output:

By length: ['fig', 'kiwi', 'date', 'apple', 'banana']
By length descending: ['banana', 'apple', 'kiwi', 'date', 'fig']
Alphabetical: ['apple', 'banana', 'date', 'fig', 'kiwi']

Notice that kiwi and date both have length 4, and in both the ascending and descending results kiwi stays before date — that is stability at work: reverse=True reverses the comparison direction, not the tie-breaking order, so equal-key elements always keep their original relative positions.

The third example makes stability explicit and useful: ranking students by score while keeping alphabetical-by-entry-order as an implicit tiebreaker.

def demonstrate_stability() -> None:
    students = [
        ('Amy', 85),
        ('Ben', 92),
        ('Cara', 85),
        ('Dev', 78),
        ('Eli', 92),
    ]
    ranked = sorted(students, key=lambda student: student[1], reverse=True)
    print('Ranked by score (ties keep original order):')
    for name, score in ranked:
        print(f'  {name}: {score}')


demonstrate_stability()

Output:

Ranked by score (ties keep original order):
  Ben: 92
  Eli: 92
  Amy: 85
  Cara: 85
  Dev: 78

Ben and Eli both scored 92; Ben appeared first in the original list, so Ben is printed first. Amy and Cara both scored 85, and again Amy (who appeared first originally) comes before Cara. Timsort never had to be told this — stability gives it for free.

How it works step by step

Because Timsort falls back to a single binary insertion sort pass on short lists, tracing that pass shows the mechanics clearly. Take [5, 3, 8, 4, 2]:

  • Start with the first element as a sorted prefix of length 1: [5 | 3, 8, 4, 2].
  • Take 3. Binary search the sorted prefix [5] for where 3 belongs → index 0. Shift 5 right: [3, 5 | 8, 4, 2].
  • Take 8. Binary search [3, 5] → belongs at index 2 (the end). No shifting needed: [3, 5, 8 | 4, 2].
  • Take 4. Binary search [3, 5, 8] → belongs at index 1 (between 3 and 5). Shift 5 and 8 right: [3, 4, 5, 8 | 2].
  • Take 2. Binary search [3, 4, 5, 8] → belongs at index 0. Shift all four right: [2, 3, 4, 5, 8].

The result, [2, 3, 4, 5, 8], matches what sorted() would produce. For a list large enough to have multiple runs, Timsort would instead find each already-ordered run (extending short ones with exactly this binary insertion process up to minrun length), push each run’s length onto a stack, and merge adjacent runs together — picking the smallest elements from each run’s front, one comparison at a time (or in galloping jumps once one side starts winning consistently) — until one fully-sorted list remains.

Common Mistakes

Mistake 1: assuming list.sort() returns the sorted list. Because sorted() returns a value, it’s an easy trap to expect the same from .sort().

numbers = [3, 1, 2]
result = numbers.sort()
print(result)

Output:

None

list.sort() mutates numbers in place and always returns None — that’s a deliberate Python convention for in-place mutators (like list.append). The fix is to either use the mutated variable directly, or use sorted() if you want an expression that produces the sorted list:

numbers = [3, 1, 2]
result = sorted(numbers)
print(result)

Output:

[1, 2, 3]

Mistake 2: sorting unorderable objects without a key. Python 3 does not define a default ordering between dictionaries (or many other mixed/complex objects), so sorting a list of dicts directly raises an error instead of silently doing something wrong — but it’s still a mistake that surprises many beginners:

records = [{'name': 'Amy', 'age': 30}, {'name': 'Ben', 'age': 25}]
sorted_records = sorted(records)
print(sorted_records)

Output (raises an exception instead of printing):

Traceback (most recent call last):
TypeError: '<' not supported between instances of 'dict' and 'dict'

Timsort needs a way to compare elements, and dictionaries don't support <. The fix is to tell it exactly what to compare with a key:

records = [{'name': 'Amy', 'age': 30}, {'name': 'Ben', 'age': 25}]
sorted_records = sorted(records, key=lambda record: record['age'])
print(sorted_records)

Output:

[{'name': 'Ben', 'age': 25}, {'name': 'Amy', 'age': 30}]

Best Practices

  • Use sorted() when you need to keep the original order around (or you're sorting a non-list iterable); use list.sort() when you don't need the original and want to avoid allocating a second list.
  • Always pass a key function rather than trying to write a custom comparator — Python 3 has no cmp parameter, and key functions are simpler and faster (called once per element, not once per comparison).
  • For attribute or index access, prefer operator.attrgetter('name') or operator.itemgetter(1) over an equivalent lambda — they're slightly faster and communicate intent clearly.
  • To sort by multiple criteria, build a tuple key, e.g. key=lambda item: (item.category, -item.priority), rather than chaining separate sort calls when the criteria aren't independent.
  • Lean on stability deliberately: if you need a secondary tiebreak that matches the data's natural order, you sometimes don't need to encode it in the key at all — the original order already provides it.
  • Don't hand-roll a sorting algorithm for production code. Timsort is implemented in C, extensively tested, and handles edge cases (duplicate keys, partially sorted data, empty lists) far better than a quick custom implementation.

Practice Exercises

1. Multi-key ranking. Given players = [('Zoe', 40), ('Al', 40), ('Max', 55)], write one call to sorted() that ranks players by score descending, breaking ties alphabetically by name (ascending). Hint: you can't just add reverse=True to a plain (score, name) key, since that would also reverse the alphabetical tiebreak — negate the score inside the key tuple instead. Expected order: Max, then Al, then Zoe.

2. Predict the stable order. Given records = [('b', 1), ('a', 1), ('c', 2)], if you sort by the second element of each tuple, what is the exact resulting list, and why does stability determine the order of the first two entries? Expected output: [('b', 1), ('a', 1), ('c', 2)].

3. Sort filenames by extension, then name. Given ['report.pdf', 'notes.txt', 'draft.pdf'], write a function that sorts by file extension first, then by the full filename. Hint: build a tuple key from the extension and the filename (str.rsplit('.', 1) or os.path.splitext can extract the extension). Expected output: ['draft.pdf', 'report.pdf', 'notes.txt'].

Summary

  • Python's sorted() and list.sort() both run Timsort, a hybrid of binary insertion sort and merge sort that exploits existing order in the data.
  • sorted() returns a new list and works on any iterable; list.sort() sorts in place on a list and returns None.
  • Time complexity: O(n) best case (already sorted or a few sorted runs), O(n log n) average and worst case — it never degrades to O(n2).
  • Space complexity: O(n) worst case, due to the temporary merge buffer.
  • Timsort is stable: elements that compare equal under the sort key keep their original relative order — essential for correct multi-key sorting.
  • Always customize ordering with key (never a removed cmp parameter), and build tuple keys for multi-criteria sorts.
  • Common pitfalls: expecting .sort() to return a value (it returns None), and sorting objects that have no natural ordering without supplying a key.