Skip to content
BENIBIX Learn

Timsort

Development🧮 Algorithms & Data StructuresSorting Algorithms

Also known as Tim Sort, TimSort

The sort Python uses. It finds runs already in order and merges them.

Think of it like

Think of it like a deck that is partly in order. Keep the neat runs, then join them.

Example

Jack sorts 100,000 prices that were in order until 50 new ones joined the end. Timsort finds the one long run, sorts the 50 and merges them, far faster than a full sort.

Why it matters

Real data is often partly sorted already. Timsort is built to spot that and skip the work, which is why sorted is so fast in practice.

Definition

Timsort is the sorting algorithm behind Python's sorted and list.sort. It looks for runs of items that are already in order. It makes short runs longer with insertion sort, then merges the runs, as merge sort does. It is stable and takes O(n log n) steps at worst. Tim Peters wrote it for Python in 2002, and Java uses it to sort objects.

Example code

python
>>> people = [("Emma", 9), ("Tom", 7), ("Jack", 9)]
>>> sorted(people, key=lambda p: p[1])
[('Tom', 7), ('Emma', 9), ('Jack', 9)]
Emma and Jack are both 9, and they keep their first order.

Common mistake

Thinking Python's sort is quicksort. It is a merge sort, so it never slows to O(n²), and equal items keep their order.

Key takeaways

  1. 1
    Finds runs. Runs already in order are kept.
  2. 2
    Merges them. Stable, and never worse than n log n.
  3. 3
    Adaptive. Fast on nearly sorted data.