Tim Sort
Overview
Tim Sort is a hybrid stable sorting algorithm derived from merge sort and insertion sort. It was designed by Tim Peters in 2002 for use in Python's list.sort() method and has since been adopted by many other languages and libraries, including Java (for non-primitive types) and Android.
Tim Sort is designed to perform well on many kinds of real-world data. It takes advantage of runs (consecutive sequences of elements that are already sorted) in the data, making it highly efficient for partially sorted arrays.
Timsort is one of the most consequential pieces of software ever written by a single
person. Every Python program that calls list.sort() or sorted()
uses it. Every Java application that sorts an array of objects with
Arrays.sort() uses it. Every Android device sorts contact lists, media
files, and app data with Timsort. It is the default sort in Kotlin, in Swift's older
stable-sort implementations, in most JavaScript engines' Array.prototype.sort,
and in dozens of other production language runtimes. Peters wrote it in 2002 to solve a
specific problem. Python's list sort was too slow on real-world data, and
over the following two decades it became the standard general-purpose sort of the
programming language industry.
The Story Behind Timsort
Tim Peters is a longtime CPython core developer, author of the "Zen of Python" (import this), and one of the small number of people whose contributions have shaped Python at a foundational level. In 2002 he took on the problem of Python's list.sort() method, which at the time used a straightforward merge sort. The merge sort was correct and stable, but Peters observed that it wasted opportunities on real-world data, data that is very often either mostly sorted, sorted in chunks, or has other structure that a naive divide-and-conquer sort ignores.
Peters spent months on the problem, iterating between profiling on real Python workloads
(mail spool sorting, log processing, database result sets) and improving the algorithm.
The result, which he documented in a legendary text file
(listsort.txt in the CPython source tree), is a synthesis of ideas from
natural merge sort, from Peter McIlroy's optimistic merging paper, from binary insertion
sort for small runs, and from a run-stack invariant that keeps merges balanced without
knowing the input distribution in advance. Peters called it "adaptive, stable, natural
mergesort with really clever merging."
Timsort was accepted into CPython 2.3 (2003) and became Python's default sort. Java adopted it for object arrays in Java 7 (2011), with modifications by Josh Bloch to fit Java's requirements. Android adopted Java's version. The algorithm's adoption across the industry is a rare case of a sort designed for one language becoming the industry default within a decade.
A notable footnote from 2015: a group of formal-methods researchers at TU Munich
(Stijn de Gouw and colleagues) attempted to formally verify Timsort using the KeY
theorem prover. In doing so they discovered a real bug in the run-stack merge invariants
that could cause an ArrayIndexOutOfBoundsException on adversarial input.
The bug had been in Java's implementation for years without triggering, because
real-world inputs did not exercise the pathological case. Python's implementation was
patched; Java's was corrected. This episode is a well-known cautionary tale in the
formal-methods community about the limits of testing and the value of proof, and it is
referenced in many algorithm-verification papers as evidence that even legendary code
can have subtle bugs undiscovered for years.
In Python 3.11 (2022), CPython actually replaced Timsort's merge-ordering policy with
powersort, an algorithm by J. Ian Munro and Sebastian Wild that
optimally schedules merges according to a different criterion. The change was
performance-focused, powersort gives near-optimal merge trees for the observed
run lengths, and the user-visible behaviour of list.sort() is
identical. But it means the sentence "Python uses Timsort" has been technically
inaccurate since 2022. It is still very nearly true, the changes are limited to
the merge scheduling, but strictly speaking Python now uses "Timsort with a
powersort merge policy."
How It Works
The algorithm works by:
- Finding Runs: Identify naturally occurring runs (ascending or descending sequences)
- Extending Runs: Extend short runs using insertion sort to a minimum run size
- Merging Runs: Merge runs using a merge sort-like approach
- Optimization: Use a stack to merge runs efficiently, maintaining balance
Tim Sort uses binary insertion sort to extend short runs up to a computed minrun,
always between 16 and 32 in CPython and Java, and merge sort to combine runs above that size.
minrun is chosen so that the number of runs is at or just below a power of two, which
keeps the final merges balanced.
Algorithm
TimSort(arr):
min_run = calculate_min_run(length of arr)
stack = [] // stack of runs, merged as we go
i = 0
while i < length of arr:
run_len = count_run(arr, i) // natural run; reverse if descending
if run_len < min_run: // too short - extend it
run_len = min(min_run, remaining)
binary_insertion_sort(arr, i, i + run_len)
stack.push((i, run_len))
merge_collapse(stack) // merge while invariants are violated
i += run_len
merge_force_collapse(stack) // merge whatever is left into one run
return arr
merge_collapse(stack): // for top three lengths A, B, C:
while invariants violated: // A > B + C and B > C
merge the smaller of the adjacent pairs
Implementation
What the pseudocode actually does that a plain merge sort does not: natural run detection, an insertion-sort extension step for short runs, the run stack with its balance invariants, and galloping mode inside the merge routine when one run is winning many consecutive comparisons in a row. Each of these was added because profiling on real Python data showed a specific class of input where the plain approach was leaving performance on the table. The result is an algorithm that is essentially optimal for the input distributions that real programs actually sort.
Two pieces make this Tim Sort rather than merge sort with an insertion-sort base case:
count_run_and_make_ascending finds naturally occurring runs instead of
chopping the array into fixed blocks, and the run stack merges them under invariants that keep
merges balanced. Both are load-bearing, without run detection there is no adaptive O(n)
best case at all.
MIN_MERGE = 32
def calculate_min_run(n):
"""Pick minrun in [16, 32] so that n/minrun is at or just below a power of 2."""
r = 0
while n >= MIN_MERGE:
r |= n & 1
n >>= 1
return n + r
def binary_insertion_sort(arr, lo, hi, start):
"""Sort arr[lo:hi], given arr[lo:start] is already sorted.
Binary search for the insertion point: O(n log n) comparisons, O(n^2) moves."""
if start <= lo:
start = lo + 1
for i in range(start, hi):
pivot = arr[i]
left, right = lo, i
while left < right:
mid = (left + right) // 2
if pivot < arr[mid]:
right = mid
else:
left = mid + 1 # <= keeps equal elements in order: STABLE
for j in range(i, left, -1):
arr[j] = arr[j - 1]
arr[left] = pivot
def count_run_and_make_ascending(arr, lo, hi):
"""Length of the natural run starting at lo, reversing it if descending."""
run_hi = lo + 1
if run_hi == hi:
return 1
if arr[run_hi] < arr[lo]: # strictly descending
while run_hi < hi and arr[run_hi] < arr[run_hi - 1]:
run_hi += 1
arr[lo:run_hi] = arr[lo:run_hi][::-1]
# Note the STRICT < above. If we accepted equal elements in a descending
# run, reversing it would swap their relative order and break stability.
else: # non-descending
while run_hi < hi and not (arr[run_hi] < arr[run_hi - 1]):
run_hi += 1
return run_hi - lo
Galloping
When merging, if one run keeps winning, Tim Sort stops comparing element by element and gallops: it binary-searches for how far the losing run can be skipped in one go. Merging a 1,000-element run into a 1,000,000-element one costs about 20 comparisons per element instead of a million.
def gallop_right(key, arr, base, length):
"""Index of the first element > key (rightmost position for stability)."""
lo, hi = 0, length
while lo < hi:
mid = (lo + hi) // 2
if key < arr[base + mid]:
hi = mid
else:
lo = mid + 1
return lo
def gallop_left(key, arr, base, length):
"""Index of the first element >= key (leftmost position)."""
lo, hi = 0, length
while lo < hi:
mid = (lo + hi) // 2
if arr[base + mid] < key:
lo = mid + 1
else:
hi = mid
return lo
def merge_at(arr, runs, i):
"""Merge runs[i] and runs[i+1], which must be adjacent."""
base1, len1 = runs[i]
base2, len2 = runs[i + 1]
runs[i] = (base1, len1 + len2)
del runs[i + 1]
# Elements of run 1 before the first element of run 2 are already in place.
k = gallop_right(arr[base2], arr, base1, len1)
base1 += k
len1 -= k
if len1 == 0:
return
# Likewise, elements of run 2 after the last element of run 1 are in place.
len2 = gallop_left(arr[base1 + len1 - 1], arr, base2, len2)
if len2 == 0:
return
# Copy the (now smaller) left run out and merge back into the gap.
left = arr[base1:base1 + len1]
i1, i2, dest = 0, base2, base1
end2 = base2 + len2
while i1 < len1 and i2 < end2:
if arr[i2] < left[i1]: # strict < means ties take from the LEFT run: STABLE
arr[dest] = arr[i2]; i2 += 1
else:
arr[dest] = left[i1]; i1 += 1
dest += 1
while i1 < len1:
arr[dest] = left[i1]; i1 += 1; dest += 1
The run stack and its invariants
Runs are pushed onto a stack and merged only when they violate two invariants, for the top three run lengths A, B, C:
A > B + C
B > C
These keep run lengths growing at least as fast as the Fibonacci sequence, which bounds the stack at O(log n) entries and guarantees merges combine runs of similar size, the property that makes the whole thing O(n log n) rather than O(n²).
A remarkable and slightly embarrassing footnote: the invariants above are the ones
Peters originally published, and for years everyone assumed they were correct. In 2015
Stijn de Gouw's team at TU Munich attempted to formally verify Timsort using the KeY
theorem prover, and their proof would not go through. They eventually discovered that
the original invariants were not sufficient to bound the stack depth in all
cases, a rare pathological input could cause the stack to grow beyond its
allocated size, throwing an ArrayIndexOutOfBoundsException. The fix was
to strengthen the invariants (also require the fourth-from-top run to be larger), and
both Python and Java patched their implementations. This story is now a standard
example in the formal-methods literature of a subtle bug in widely-deployed code that
only formal verification uncovered.
def merge_collapse(arr, runs):
"""Restore the stack invariants by merging until they hold."""
while len(runs) > 1:
n = len(runs) - 2
if (n > 0 and runs[n-1][1] <= runs[n][1] + runs[n+1][1]) or \
(n > 1 and runs[n-2][1] <= runs[n-1][1] + runs[n][1]):
if runs[n-1][1] < runs[n+1][1]:
n -= 1 # merge with the smaller neighbour
elif runs[n][1] > runs[n+1][1]:
break # invariants hold
merge_at(arr, runs, n)
def merge_force_collapse(arr, runs):
"""Merge everything down to one run at the end."""
while len(runs) > 1:
n = len(runs) - 2
if n > 0 and runs[n-1][1] < runs[n+1][1]:
n -= 1
merge_at(arr, runs, n)
def tim_sort(arr):
n = len(arr)
if n < 2:
return arr
# Small arrays: one run plus a binary insertion sort, no merging at all.
if n < MIN_MERGE:
run_len = count_run_and_make_ascending(arr, 0, n)
binary_insertion_sort(arr, 0, n, run_len)
return arr
min_run = calculate_min_run(n)
runs = [] # stack of (start_index, length)
lo = 0
while lo < n:
run_len = count_run_and_make_ascending(arr, lo, n)
if run_len < min_run: # extend a short run up to min_run
force = min(min_run, n - lo)
binary_insertion_sort(arr, lo, lo + force, lo + run_len)
run_len = force
runs.append((lo, run_len))
merge_collapse(arr, runs)
lo += run_len
merge_force_collapse(arr, runs)
return arr
The adaptivity is measurable. Counting merge operations on 5,000 elements:
already sorted -> 0 merges one natural run, nothing to merge: O(n)
reverse sorted -> 0 merges one descending run, reversed in place: O(n)
random -> 249 merges O(n log n)
Complexity Analysis
- Time Complexity:
- Best Case: O(n) - when array is already sorted
- Average Case: O(n log n)
- Worst Case: O(n log n)
- Space Complexity: O(n) - for temporary arrays during merging
Tim Sort performs exceptionally well on real-world data because it exploits existing order, which real data usually has. The O(n) best case comes specifically from natural run detection: an already sorted array is one run, and there is nothing to merge.
A note on the invariants. In 2015 de Gouw et al. formally verified the run-stack
logic and found the invariant check was insufficient, a sufficiently adversarial
input could overflow the fixed-size run stack, and they produced a concrete array that crashed
java.util.Collections.sort() with an ArrayIndexOutOfBoundsException. Java
patched it by enlarging the stack; Python patched the invariant check itself.
And a currency note. Since Python 3.11, CPython no longer uses Tim Sort's original merge-ordering policy. It uses powersort (Munro & Wild, 2018), which chooses the merge order using a rule derived from optimal binary search trees. Run detection, galloping and binary insertion sort are all unchanged, only the decision of which two runs to merge next differs, and it is provably closer to optimal. So "Python uses Timsort" is still true of the name and most of the machinery, but not of the merge policy.
Characteristics
- Stable: Yes - maintains relative order of equal elements
- In-place: No - requires O(n) extra space for merging
- Adaptive: Yes - very efficient for partially sorted data
- Online: No - requires the entire array
- Hybrid: Yes - combines insertion sort and merge sort
When to Use Tim Sort
Tim Sort is ideal when:
- You need a general-purpose, stable sorting algorithm
- Data is likely to be partially sorted
- You want consistent O(n log n) performance
- Stability is important (maintaining order of equal elements)
- Used as default sorting in many programming languages
Tim Sort is the default sorting algorithm in:
- Python (list.sort() and sorted())
- Java (for non-primitive types)
- Android platform
- Many other modern systems
Example
Tim Sort excels when data has natural runs:
A 9-element array never actually reaches the merge machinery, 9 < MIN_MERGE, so Tim Sort detects one run and binary-insertion-sorts the rest. To see runs and merges you need an array of at least 32 elements. Here is a 40-element example with deliberate structure:
Array (40 elements):
[1..12 ascending] ++ [30..21 descending] ++ [random 18 elements]
n = 40, so minrun = calculate_min_run(40) = 20
Step 1: count_run_and_make_ascending at index 0
finds the natural ascending run 1..12 -> run_len = 12
12 < minrun, so binary-insertion-sort out to 20 elements
push (base=0, len=20) stack: [20]
Step 2: count_run_and_make_ascending at index 20
finds a strictly DESCENDING run, reverses it in place
extends to minrun the same way
push (base=20, len=20) stack: [20, 20]
merge_collapse: B > C fails (20 > 20 is false) -> merge
merge_at galloping: the two runs barely overlap, so most elements
are skipped without comparison stack: [40]
Step 3: lo = 40 = n, loop ends
merge_force_collapse: only one run left, nothing to do
Final: fully sorted, with 1 merge instead of the ~5 a fixed-block
bottom-up mergesort would perform on the same input.
On input that is already sorted, step 1 finds a single run covering the whole array and the merge loop never executes at all, that is the O(n) best case.
Related Algorithms
Explore other sorting algorithms:
- Insertion Sort - Used as subroutine in Tim Sort
- Merge Sort - Base algorithm for Tim Sort
- Quick Sort - Fast average case alternative
- Back to Sorting Algorithms Overview