Timsort

Timsort is a hybrid, stable sorting algorithm that combines merge sort with insertion sort to run quickly on the partially ordered data that turns up in practice. Tim Peters designed it for Python in 2002, and it still powers sorted() and the .sort() method on every list.

The core idea is to exploit order that already exists. Timsort first scans the input for runs, which are maximal stretches that are already ascending or strictly descending, and it reverses any descending run in place.

When a natural run falls short of a minimum length, typically between 32 and 64 elements, Timsort extends it with a binary insertion sort, which uses binary search to find where each new element belongs. Those minimum lengths are chosen so the run count stays close to a power of two, which keeps the later merges balanced.

Timsort then merges the runs pairwise using a stack of pending runs, choosing an order that avoids repeatedly merging a short run into a much longer one. Since Python 3.11, CPython picks that order with powersort, a rule that comes provably close to the best possible merge tree for the runs it found.

A technique called galloping speeds up each merge: when one run keeps winning, the algorithm uses exponential search to copy a whole block of its elements at once instead of one at a time.

Step through the phases below to watch Timsort detect runs, reverse a descending run in place, pad a short run to the minimum length, and merge the runs pairwise. Switching the input pattern shows how much less work already-ordered data takes.

Interactive diagram — enable JavaScript to view.

A few properties define how Timsort behaves:

  • Stable: Equal elements keep their original relative order, so multi-key sorts stack cleanly.
  • Adaptive: Nearly sorted input approaches O(n) time complexity, while the average and worst case stay at O(n log n).
  • Extra memory: Merging borrows up to O(n) of temporary space for combining runs.

Beyond Python, Timsort backs the default object sort in Java and Android, the V8 engine behind Chrome and Node.js, and Swift, which makes it one of the most widely deployed sorting algorithms in production software.

Sorting Algorithms in Python

Tutorial

Sorting Algorithms in Python

In this tutorial, you'll learn all about five different sorting algorithms in Python from both a theoretical and a practical standpoint. You'll also learn several related and important concepts, including Big O notation and recursion.

intermediate algorithms python

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated Aug. 6, 2026
Computer Science Glossary Share Feedback