Timsort is a hybrid stable sort derived from mergesort and insertion sort. It is the algorithm behind Python's built-in sorted() and list.sort(), and Java's Arrays.sort on object arrays.
The sections below trace run detection on a concrete array, explain the run stack and galloping merges, and give a simplified implementation that shows the core ideas.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n) |
Θ(n log n) |
O(n log n) |
O(n) |
Walk the input identifying naturally-ordered subsequences ("runs"). Short runs are extended to a minimum length using insertion sort. Runs are pushed onto a stack and merged according to invariants that balance run lengths, keeping the merge tree shallow. The result is O(n) on already-sorted or reverse-sorted input and O(n log n) otherwise — and stable.
# In production: just call sorted() — it IS Timsort.
data = [3, 6, 1, 8, 2, 9, 4]
print(sorted(data)) # [1, 2, 3, 4, 6, 8, 9]
data.sort() # in-place
print(data)
# Sketch of the core idea: detect runs, extend short ones with
# insertion sort, then merge runs pairwise.
def insertion_sort(a, lo, hi):
for i in range(lo + 1, hi):
x = a[i]; j = i - 1
while j >= lo and a[j] > x:
a[j + 1] = a[j]; j -= 1
a[j + 1] = x
def timsort_sketch(a, min_run=32):
n = len(a)
for start in range(0, n, min_run):
insertion_sort(a, start, min(start + min_run, n))
size = min_run
while size < n:
for left in range(0, n, 2 * size):
mid = min(left + size, n)
right = min(left + 2 * size, n)
a[left:right] = sorted(a[left:right]) # placeholder merge
size *= 2
return aTimsort begins by scanning for runs: maximal stretches that are already non-decreasing, or strictly decreasing. In the example, 1 4 7 9 is an ascending run. The next stretch 8 5 2 is strictly descending, so Timsort reverses it in place to 2 5 8; the requirement of strict descent is what keeps the reversal stable, because no equal elements get swapped. The tail 3 6 is a short ascending run. Real implementations require each run to be at least minrun long (a value between 32 and 64 chosen from n), and extend shorter runs with binary insertion sort. With an input this small, the entire array would simply be insertion-sorted, but the trace shows the logic that applies at scale.
Each run is pushed onto a stack. After every push, the algorithm checks invariants on the top few run lengths and merges adjacent runs until they hold. The classic rules are that, for the top three run lengths A, B and C, A > B + C and B > C. These keep merges roughly balanced, like a mergesort tree, while letting long natural runs stay intact. Merges use a temporary buffer the size of the smaller run, and a galloping mode: when one run wins many comparisons in a row, Timsort switches to exponential search to find how many elements to copy in one block. On data with large ordered regions this skips most comparisons. Recent CPython versions replaced the original stack rules with the “powersort” merge policy, which computes merge order from run positions; the run detection, minrun and galloping ideas are unchanged.
from bisect import insort
MINRUN = 4
def find_run(a, lo):
hi = lo + 1
if hi == len(a):
return hi
if a[hi] < a[lo]: # strictly descending
while hi < len(a) and a[hi] < a[hi - 1]:
hi += 1
a[lo:hi] = reversed(a[lo:hi])
else: # non-decreasing
while hi < len(a) and a[hi] >= a[hi - 1]:
hi += 1
return hi
def merge(x, y):
out, i, j = [], 0, 0
while i < len(x) and j < len(y):
if y[j] < x[i]:
out.append(y[j]); j += 1
else:
out.append(x[i]); i += 1
return out + x[i:] + y[j:]
def simple_timsort(data):
a, runs, lo = list(data), [], 0
while lo < len(a):
hi = find_run(a, lo)
run = a[lo:hi]
while len(run) < MINRUN and hi < len(a): # extend short run
insort(run, a[hi]); hi += 1
runs.append(run)
lo = hi
while len(runs) > 1: # pairwise merging
runs = [merge(runs[k], runs[k + 1]) if k + 1 < len(runs) else runs[k]
for k in range(0, len(runs), 2)]
return runs[0] if runs else []
print(simple_timsort([1, 4, 7, 9, 8, 5, 2, 3, 6])) # [1, 2, 3, 4, 5, 6, 7, 8, 9]This sketch keeps the three core ideas — run detection with reversal, extension to a minimum run length with insertion, and stable merging — and replaces the stack invariants and galloping with plain pairwise merges. It is for understanding only; use sorted() or list.sort() in real code, which are implemented in C. Note that insort is stable for already-placed items but inserts after equal elements, which matches the stable behaviour needed here.
Timsort is the default sort in Python and is used by Java for object arrays and by Android and V8 for similar reasons. It performs best on real-world data that is partially ordered: appending a few records to a sorted list, sorting log lines that are mostly chronological, or concatenating several sorted files. Such inputs approach O(n). On uniformly random data it behaves like a well-tuned mergesort with O(n log n) comparisons and O(n) auxiliary space in the worst case. If memory is tightly constrained or stability does not matter, an in-place introsort may be preferable.
key= function is faster in Python than a comparison function via cmp_to_key, because keys are computed once per element.ValueError in CPython.Mergesort explains the merge step Timsort builds on, and Insertion Sort the method used to build minimum-length runs. Compare with Quicksort for an unstable in-place alternative.