Timsort
This page introduces Timsort, a hybrid, stable sorting algorithm.
Introduction
Tim Peters, a Python core developer, designed Timsort in 2002 for use in Python. It combines the strengths of insertion sort and merge sort and is carefully tuned to exploit the order already present in the data, which makes it especially good on data sets that contain many partially sorted subsequences. CPython has used Timsort since version 2.3; in version 3.11 it replaced Timsort's merge policy with Powersort1. Timsort is widely used in other programming environments too: Java SE 7, for example, uses it to sort arrays of non-primitive objects.
This page describes classic Timsort and follows the merge rules of CPython 3.6.5, in which the bug in maintaining the stack invariant is already fixed2.
Steps
The key idea of Timsort is to find the order the data already has and exploit it to sort faster. Its main steps are:
- Finding runs: scan the array to be sorted and find the contiguous subsequences that are already sorted (runs);
- Extending runs: if a run found this way is shorter than
MIN_RUN, extend it with insertion sort; - Merging runs: Timsort maintains a special stack and follows a specific merge policy to merge the runs on the stack into longer sorted sequences.
Finding runs
Timsort first scans the array from left to right and finds contiguous sorted sequences, which are called runs:
- Ascending run: while the next element is greater than or equal to the previous one, keep extending the run.
- Descending run: while the next element is less than the previous one, keep extending the run; then reverse the run to make it ascending.
Extending runs
To sort small amounts of data more efficiently, Timsort introduces a minimum run length, MIN_RUN. Its value is usually computed dynamically from the length of the array to be sorted and typically lies between \(32\) and \(64\).
- If the run is at least
MIN_RUNlong, nothing more is needed: push the run onto the stack. - If the run is shorter than
MIN_RUN, use binary insertion sort to insert the elements that follow the run into it until its length reachesMIN_RUN, then push it onto the stack.
Merging runs
Timsort manages and controls its merge sort with a stack. The stack holds the sorted runs found so far, and specific merge rules control how the runs on it are merged. Their purpose is to keep the merges balanced and the sort stable.
Merge rules
Timsort is a stable sorting algorithm: equal elements keep their original relative order after sorting. To guarantee this, Timsort only ever merges adjacent, consecutive runs and never merges non-adjacent runs directly. Non-adjacent runs may contain equal elements, and merging them directly would very likely disturb the relative order of those elements.
To keep the merges balanced and limit the number of runs waiting to be merged, Timsort also requires every three adjacent runs on the stack to satisfy the following invariant. Call the three runs X, Y and Z, going from the top of the stack towards the bottom:
- Condition 1:
len(Z) > len(Y) + len(X) - Condition 2:
len(Y) > len(X)
When the stack holds only two runs, len(Y) > len(X) is still required. Each time a new run is pushed, mergeCollapse examines up to four runs at the top of the stack, called X, Y, Z and W from the top down, and decides whether to merge by going through the following cases in order2:
- if
len(Z) <= len(Y) + len(X)orlen(W) <= len(Z) + len(Y), merge Y with the shorter of X and Z, choosing X when X and Z have the same length; - otherwise, if
len(Y) <= len(X), merge Y and X; - otherwise, stop merging for this round and go on to find the next run.
Only the conditions whose runs all exist are checked. After each merge, X, Y, Z and W are determined anew and the process repeats. The figure below shows how the stack changes when X and Y are merged.
Why does the fourth run have to be checked?
If only the top three runs are checked, a merge can leave a violation of the invariant deeper in the stack unnoticed. For example, push runs of lengths \(240,160,50,40,60\) in this order (from the bottom of the stack to the top). The old rule merges \(50\) and \(40\), which gives \(240,160,90,60\). Now the top of the stack satisfies \(160>90+60\) and \(90>60\), but deeper down we have \(240\le160+90\).
This flaw breaks the guarantee of a fixed stack capacity, which is derived from the invariant holding on the whole stack. CPython fixed the check in 20154.
Merge optimizations
To merge runs of different lengths faster and with less extra space, Timsort uses binary search before a merge to pin down exactly which elements have to be processed, and merges only the part that has to move. It does this as follows:
-
Finding the insertion points: use binary search to find where the first element of the second run would be inserted in the first run, and where the last element of the first run would be inserted in the second run. This narrows down the range to be merged, so that only the elements that have to move are processed;
-
Temporary buffer: traditional in-place merging algorithms are too slow, because they move a great many elements. To cut this cost, Timsort uses a temporary buffer: it copies the shorter run into the buffer and then copies the elements from the buffer back into the original array step by step.
For example, suppose there are two runs A and B:
- Run A: \([1, 2, 3, 6, 10]\)
- Run B: \([4, 5, 7, 9, 12, 14, 17]\)
Binary search determines that:
- Element \(4\) should be inserted at the fourth position of run A.
- Element \(10\) should be inserted at the fifth position of run B.
So the first \(3\) elements of run A and the last \(3\) elements of run B are already in the right place and need no work. Only \([6, 10]\) from run A and \([4, 5, 7, 9]\) from run B have to be merged, as the figure below shows:
Galloping mode
To make merging faster still, Timsort introduces galloping mode. A standard merge compares the elements of the two runs one at a time and puts the smaller one into the result array. But if one run has many consecutive elements that are smaller than the current element of the other run, comparing them one by one is wasted work.
To solve this problem, Timsort sets a threshold Min_Gallop (default value \(7\)). When the elements of one run have won Min_Gallop comparisons in a row, the algorithm enters galloping mode, which locates element positions quickly in the following steps:
- Exponential search: starting from the current position, the algorithm searches one of the runs with exponentially growing steps \((1, 2, 4, 8, \dots)\) until it finds a range that contains the target element;
- Binary search: once the range containing the target element is known, the algorithm uses binary search inside that range to find the exact position of the target element.
In this way Timsort skips a large number of unnecessary comparisons: it quickly handles a stretch of consecutive smaller (or larger) elements of one run and moves them into the merge result in bulk.
Galloping mode is not more efficient in every case, however. On some data distributions it can lead to more comparisons. Timsort therefore adjusts dynamically:
- Adjusting the threshold:
Min_Gallopis kept as a variable parameter. When galloping mode works well (elements are taken from the same run many times in a row),Min_Gallopis decreased by \(1\), which encourages further galloping; when it works poorly (the merge switches between the two runs frequently),Min_Gallopis increased by \(1\), so that galloping mode is used less often.
By adjusting the value of Min_Gallop dynamically, the algorithm strikes a balance between ordinary merging and galloping mode that fits the actual data. On partially sorted or highly sorted data, galloping mode improves efficiency significantly and brings the performance of Timsort close to \(O(n)\); on random data, the algorithm gradually shifts towards ordinary merging, which guarantees a time complexity of \(O(n \log n)\).
Complexity
The time complexity of Timsort depends on how sorted the data is:
- Best case: \(O(n)\)
- When the data is already sorted or nearly sorted, the runs the algorithm finds have length close to \(n\) and fewer merges are needed, so the complexity approaches \(O(n)\).
- Worst case: \(O(n \log n)\)
- With \(r\) runs, \(r-1\) two-way merges are needed in the end; the number of merges must not be written as \(O(\log n)\).
Finding the runs costs \(O(n)\), and extending the short runs with a bounded MIN_RUN also costs \(O(n)\) in total. The cost of merging is the sum, over all merges, of the lengths of the two runs merged, which equals the sum, over all elements, of the number of merges the element takes part in. The upper bound on this sum depends on the specific merge rules. For the merge rules of the Python 3.6.5 TimSort analyzed in the literature3, amortized analysis gives \(O(n+n\log r)\), and hence \(O(n\log n)\) in the worst case.
As for space, Timsort needs roughly \(O(n)\) extra space to store the stack and the temporary buffer, so its total space complexity is \(O(n)\).
Implementation
Pseudocode
References and notes
- Timsort
- Tim Peters's design notes (CPython 3.6.5; for the merge conditions, the code of that version is authoritative)
- Java implementation
- C implementation (CPython 3.6.5)
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Great-designer, shuzhouliu, 24OI-bot, yyyu-star, HeRaNO, Tiphereth-A, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.