Timsort Algorithm: How Python Has Sorted Lists Since 2002

⏱️ Reading time: 8 min

Guido van Rossum announced on November 11, 2026, that Tim Peters, author of the Timsort algorithm and the Zen of Python (PEP 20), died on July 15 of that year. Long before writing either of them, Peters convinced Van Rossum that int and float should mix in the same arithmetic operation, according to the original announcement.

📑 En este artículo

1. The Timsort algorithm: what it is and where it came from
2. How Timsort decides when to merge the two techniques
3. Why it matters if you code in Python, Java or Android
4. Timsort vs. quicksort, merge sort and Java’s dual-pivot quicksort
5. When Timsort is not the best choice
6. The Zen of Python: Tim Peters’s other great legacy
7. References

The name behind millions of programs that run every day without anyone knowing it is that creation: Timsort. Peters designed it in 2002 to sort Python lists, and according to the same announcement from Van Rossum, Java and Android later adopted it for their own collections.

The Timsort algorithm: what it is and where it came from

Timsort is a hybrid sorting algorithm. It combines insertion sort for small segments with an adaptive version of merge sort for the rest of the list. Since 2002 it has run behind list.sort() and sorted() in Python, and it is also what Java uses to sort arrays of objects, according to Van Rossum’s account of its creator.

Combining two sorting techniques is not a new idea, but the way Timsort decides when to use each one is. Instead of assuming the data arrives in any order, the algorithm first looks for runs: stretches of the list that happen to already be sorted, ascending or descending, by pure chance. Real-world data is rarely random. It usually has dates, names or IDs that are partially sorted, and Timsort exploits exactly that.

How Timsort decides when to merge the two techniques

The algorithm scans the list from left to right and groups consecutive elements into runs. If a run is shorter than a minimum threshold (typically between 32 and 64 elements, depending on the total size of the list), Timsort extends it with insertion sort until it reaches that threshold. Insertion sort is slow on large lists, but very fast on short stretches, and that is where it wins.

Each finished run is pushed onto a stack of pending runs. Timsort keeps an invariant over the relative sizes of that stack: each run must be larger than the sum of the next two. When that breaks, it merges the neighboring runs using a version of merge sort that uses less memory than the classic one.

If one of the two runs keeps “winning” through several consecutive merges, the algorithm switches to galloping mode. Instead of comparing element by element, it uses binary jumps to find where to insert a whole block of the losing run at once. Galloping mode is the least intuitive part of the design, and the one that most distinguishes Timsort from a textbook merge sort.

The technical note that Tim Peters wrote for the CPython source code describes the full reasoning, including the exact formula for calculating the minimum size of each run.

flowchart TD
A["Input list"] --> B["Detect ascending or descending run"]
B --> C{"Run shorter than minimum"}
C -- "yes" --> D["Extend with insertion sort"]
C -- "no" --> E["Push run onto stack"]
D --> E
E --> F{"Size invariant broken"}
F -- "yes" --> G["Merge neighboring runs with adaptive merge sort"]
F -- "no" --> H["Continue reading the list"]
G --> H
H --> I["List fully sorted"]

Why it matters if you code in Python, Java or Android

For backend developers writing Python, Timsort is why sorting lists of dictionaries, tuples or database records is fast even when that data already arrives nearly sorted, for example by creation date. There is nothing to configure: sorted(data, key=...) already runs on Timsort.

For those working in Java or Android, the same algorithm sorts any array of objects. If your team uses Collections.sort() or Arrays.sort() on an array of objects, it is running Timsort without knowing it, just like in Python.

And for those designing their own data structures, Timsort is a case study in a broader principle. It optimizes for the common case of real-world data instead of the theoretical worst case. That is exactly what separates a textbook algorithm from one that survives 24 years in production.

Timsort vs. quicksort, merge sort and Java’s dual-pivot quicksort

No sorting algorithm wins at everything. The table below compares Timsort with the three best-known alternatives for the same problem.

Algorithm	Stable	Worst case	Advantage with real-world data	Where it’s used
Timsort	Yes	O(n log n)	Exploits already-sorted runs; nearly free on partially sorted data	Python list.sort(), Java Arrays.sort() for objects, Android
Classic quicksort	No	O(n²)	Fast on average, but does not take advantage of existing order	Variants of qsort in C and several standard libraries
Classic merge sort	Yes	O(n log n)	Guarantees the worst case, but merges even when the data is already sorted	Basis for structures that require stability without adapting to the input
Dual-pivot quicksort	No	O(n log n) on average	Very fast on arrays of primitives, with no stability overhead	Java Arrays.sort() for primitive types like int and double

The row that usually surprises people most is the last one, because Java does not use Timsort for everything. For arrays of int, double or char it uses a dual-pivot quicksort, because those arrays do not need stability (there are no equal objects with distinct identity to preserve), and dual-pivot quicksort is faster there. Timsort is reserved for arrays of objects, where stability does matter.

When Timsort is not the best choice

Timsort has an extra memory cost, because it needs a temporary buffer for the merges. On systems with very tight memory, like microcontrollers, that cost weighs more than it does on a typical backend server.

It is also not the fastest possible option for arrays of standalone primitive numbers with no prior order. There, a well-implemented quicksort, without the bookkeeping of runs and without guaranteeing stability, can beat it. That is why Java keeps the two cases separate instead of using Timsort for everything.

And its adaptive behavior, which is its greatest strength, also complicates benchmarks. The same algorithm can take very different amounts of time depending on how sorted the input data already is, so comparing Timsort against another algorithm with a single test case almost never tells the whole story.

The Zen of Python: Tim Peters’s other great legacy

While designing Timsort, Peters was already known on the Python mailing list as “Timbot,” according to Van Rossum’s announcement. He answered users’ questions with such consistent humor that it became his signature, always marked with <wink>. That tone, half technical and half informal, runs through the Zen of Python, the list of aphorisms that still appears when you type import this in any Python interpreter.

The Zen is not a syntax manual: it is a guide to judgment. Phrases like “explicit is better than implicit” or “simple is better than complex” do not dictate how to write code, but how to discuss a design decision when two solutions are both technically valid. A comment on Hacker News recalls, for example, that Python’s explicit self parameter in methods, unlike Java or C++, was debated with that same criterion, and that Peters played an active role in that discussion.

Van Rossum summed up Peters’s influence in one line of his announcement: “It’s hard to overestimate Tim’s influence on Python.” He added that before writing the Zen, Tim had already convinced him to mix int and float in the same arithmetic operation, because that is what any user would expect. That kind of decision, small but with an effect on millions of programs, is what the Zen tried to make repeatable for the rest of the team.

📌 Note: The full announcement, with more anecdotes from other Python core developers, is in the original thread on discuss.python.org.

Neither legacy depends on the other to stay relevant. Timsort keeps sorting lists even though nobody thinks about its author when writing sorted(), and the Zen keeps getting quoted in code reviews even when whoever quotes it does not know who wrote it. That is the clearest proof of how well both were designed. They outlived the need for their author.

References

• In Memoriam: Tim Peters 1952-2026: Guido van Rossum’s announcement with the date of Peters’s death and the origin of Timsort.
• listsort.txt in the CPython repository: Tim Peters’s original technical note on Timsort’s design.
• PEP 20: The Zen of Python: the full text of the aphorisms written by Tim Peters.
• Hacker News thread about Tim Peters’s death: reactions and anecdotes from the community.

Featured image: Foto de Hitesh Choudhary en Unsplash

How each article is made (sources, testing and editorial criteria): How we work.