SortingAlgorithmaka Tim Peters' sort, adaptive merge sort, natural merge sort (hybrid)

TimSort

Adaptive, stable hybrid of merge sort and insertion sort that exploits existing sorted runs; the default sort in Python and Java.

▶ Visualize Pattern: Intervals Practice (3)

Progress

Overview

TimSort (Tim Peters, 2002) is the sort behind Python's list.sort() / sorted(), Java's Arrays.sort for objects and Collections.sort, Android, V8's Array.prototype.sort, Rust's slice::sort (a variant), and Swift. It is a stable, adaptive Merge Sort that scans the input for naturally occurring runs (already ascending or strictly descending stretches, reversed in place), extends short runs to a minimum length (minrun, 32–64) with binary Insertion Sort, and merges runs using a stack with balance invariants.

On random data it is a well-tuned merge sort at O(n log n); on data with structure (sorted, reverse sorted, a few appended items, concatenated sorted chunks) it approaches O(n) — real-world data is very often partially ordered. The merge step uses galloping (Exponential Search) to skip long stretches when one run's elements are consistently smaller. Space is O(n) worst case for the merge buffer (only min(len(run1), len(run2)) is copied). It is not in-place. C++'s std::sort deliberately chose introsort instead because the STL contract does not require stability; std::stable_sort is a merge sort.

comparisonstableadaptiveO(n log n)hybridnatural runslibrary sort

Intuition

A mental model before the formal terms.

Real data is rarely random: a log file is mostly chronological, a re-sorted list has a few new items. Instead of blindly splitting into halves, walk the array and notice "this stretch is already sorted, this one is sorted backwards" — treat each as a finished piece. Make tiny pieces a bit bigger by hand (insertion sort), then merge pieces two at a time, always merging similar-sized pieces so the merge tree stays balanced. When merging, if one piece keeps winning, gallop ahead by doubling steps instead of comparing one at a time.

How it works

Compute minrun from n (choose so that n / minrun is a power of two or slightly below, between 32 and 64).
Scan left to right. Detect the next run: a maximal non-decreasing stretch, or a strictly decreasing stretch which is reversed in place (strictness keeps stability). If the run is shorter than minrun, extend it to min(minrun, remaining) using binary insertion sort.
Push the run (start, length) onto a stack. Restore the invariants for the top three runs A, B, C (C on top): len(A) > len(B) + len(C) and len(B) > len(C). If violated, merge B with the smaller of A and C. This keeps the stack size O(log n) and merges balanced.
Merge two adjacent runs: first use binary search to find where the second run's first element belongs in the first run and where the first run's last element belongs in the second — elements outside those bounds are already in place. Copy the smaller run to a temp buffer and merge from the left (merge_lo) or right (merge_hi).
During a merge, count consecutive wins by one side; after MIN_GALLOP (7) wins, switch to galloping mode: exponential search then binary search to find how many elements to copy in one block. Adapt min_gallop up or down depending on whether galloping paid off.
After the scan, collapse the stack by merging all remaining runs.

Why it works

Correctness is that of merge sort: every run is sorted (natural or by insertion sort), and merging adjacent sorted runs yields a sorted run; stability holds because ties go to the left run and descending runs are only reversed when strictly descending.

The stack invariants ensure run lengths grow at least like Fibonacci numbers from top to bottom, so there are O(log n) runs on the stack and each element takes part in O(log n) merges — O(n log n) worst case. (The original invariant had a subtle bug found by formal verification in 2015; Python and Java were patched to check the top four runs.)

Adaptivity: if the input has r natural runs, the cost is O(n + n log r); for r = 1 (sorted or reverse sorted) it is O(n).

Galloping makes merging two runs where one mostly precedes the other cost O(log) per block rather than O(len).

Recognition

How to tell a problem wants this.

Any question about what Python / Java's built-in sort does, or why it is fast on partially sorted data.
Data with pre-existing order — appending items to a sorted list, merging sorted chunks, sorting by a second key after a first.
A stable O(n log n) sort that should be near-linear on nearly sorted input.

“overlapping intervals” → Intervals “merge k sorted” → Divide and Conquer

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Merge Sort visualization.

Array — Comma or space separated numbers, up to 40

1/54Start with 8 elements. Merge sort splits the array in halves until pieces of size one, then merges sorted pieces back together.

Left halfRight halfHeads being comparedMerged / sorted

PseudocodeLearn Merge Sort →

1mergeSort(a, lo, hi):
2  if lo >= hi: return
3  mid = (lo + hi) // 2
4  mergeSort(a, lo, mid)
5  mergeSort(a, mid+1, hi)
6  merge(a, lo, mid, hi):
7    i = lo, j = mid+1, buf = []
8    while i <= mid and j <= hi:
9      if a[i] <= a[j]: buf.push(a[i++]) else buf.push(a[j++])
10    append leftovers of both halves to buf
11    copy buf back into a[lo..hi]

Complexity

best O(n log n)

avg O(n log n)

worst O(n log n)

space O(n)

Speed

Pseudocode

1minrun = computeMinrun(n); stack = []
2i = 0
3while i < n:
4  run = findRun(a, i)  # ascending, or strictly descending then reversed
5  if len(run) < minrun: extend with binary insertion sort to min(minrun, n - i)
6  stack.push(run); i += len(run)
7  while stack invariants violated: merge top runs (with galloping)
8while len(stack) > 1: merge top two runs

Implementations

1from bisect import bisect_right
2 
3# TimSort: an adaptive, stable hybrid. Find naturally sorted RUNS, extend the
4# short ones with insertion sort, then merge runs under invariants that keep
5# the merge tree balanced. This is a faithful simplified version of what
6# CPython's list.sort() actually does — the real one adds galloping merges.
7 
8 
91 · minrun keeps the number of runs close to a power of two, so the
10# merges stay balanced. Real TimSort picks 32..64; this is the same rule.
11def compute_min_run(n: int) -> int:
12    r = 0
13    while n >= 64:
14        r |= n & 1
15        n >>= 1
16    return n + r
17 
18 
192 · Binary insertion sort — stable, and fast on the short runs minrun makes
20def binary_insertion_sort(a: list[int], lo: int, hi: int) -> None:
21    for i in range(lo + 1, hi):
22        key = a[i]
23        # bisect_right keeps it STABLE: equal elements insert after, not before
24        pos = bisect_right(a, key, lo, i)
25        a[pos + 1 : i + 1] = a[pos:i]
26        a[pos] = key
27 
28 
293 · A descending run is reversed in place, which is what makes TimSort
30# O(n) on reverse-sorted input as well as on sorted input
31def find_run(a: list[int], lo: int, hi: int) -> int:
32    if hi - lo < 2:
33        return hi
34    i = lo + 1
35    if a[i] < a[i - 1]:  # strictly descending
36        while i < hi and a[i] < a[i - 1]:
37            i += 1
38        a[lo:i] = a[lo:i][::-1]
39    else:  # non-descending
40        while i < hi and a[i] >= a[i - 1]:
41            i += 1
42    return i
43 
44 
454 · Merge two adjacent sorted runs; copying only the left half halves the
46# scratch space compared with a full merge buffer
47def merge_runs(a: list[int], lo: int, mid: int, hi: int) -> None:
48    tmp = a[lo:mid]
49    i, j, k = 0, mid, lo
50    while i < len(tmp) and j < hi:
51        if a[j] < tmp[i]:
52            a[k] = a[j]
53            j += 1
54        else:
55            a[k] = tmp[i]
56            i += 1
57        k += 1
58    while i < len(tmp):
59        a[k] = tmp[i]
60        i += 1
61        k += 1
62 
63 
645 · The driver: build runs of at least minrun, then merge them pairwise
65def tim_sort(a: list[int]) -> None:
66    n = len(a)
67    if n < 2:
68        return
69    min_run = compute_min_run(n)
70    runs: list[tuple[int, int]] = []
71 
72    lo = 0
73    while lo < n:
74        hi = find_run(a, lo, n)
75        if hi - lo < min_run:
76            hi = min(lo + min_run, n)
77            binary_insertion_sort(a, lo, hi)
78        runs.append((lo, hi))
79        lo = hi
80 
81    while len(runs) > 1:
82        nxt: list[tuple[int, int]] = []
83        for i in range(0, len(runs), 2):
84            if i + 1 < len(runs):
85                merge_runs(a, runs[i][0], runs[i][1], runs[i + 1][1])
86                nxt.append((runs[i][0], runs[i + 1][1]))
87            else:
88                nxt.append(runs[i])
89        runs = nxt

Walkthrough

bisect_right(a, key, lo, i) is the stable insertion point, searching only the already-sorted prefix via the lo/hi arguments.
a[pos + 1 : i + 1] = a[pos:i] shifts the block in one slice assignment rather than an element loop — a C-level memmove instead of Python iterations.
a[lo:i] = a[lo:i][::-1] reverses the descending run via slice assignment, which is again a single C-level operation.
tmp = a[lo:mid] copies only the left run, matching the other three languages.
This *is* what list.sort() does internally, so the hand-written version is strictly slower — the value is in seeing the run detection and the stability decisions.

Complexity (this implementation)

time O(n) best case on sorted or reverse-sorted input, O(n log n) worst case · space O(n) for the slice copies

CPython's list.sort() is TimSort implemented in C, so this version is several hundred times slower on the same input.

Language notes

list.sort() and sorted() are TimSort, invented for CPython by Tim Peters and later adopted by Java and V8 — this entry reimplements the language's own sort.
bisect_right versus bisect_left is exactly the stability decision, and bisect takes lo/hi so no slicing is needed.
Slice assignment for the shift and the reverse turns two Python loops into two C memmoves, which is the single biggest speed difference from a naive transcription.
functools.cmp_to_key exists for comparator-based sorting but is much slower than a key= function.

Common mistakes in this language

Using bisect_left and losing stability.
Writing the shift as a Python for loop instead of slice assignment.
Reversing a run detected with a non-strict <= comparison, which breaks stability.

Language differences that matter here

TimSort is the standard library sort in Python (list.sort) and JavaScript (V8 since 2018), so both reimplementations are educational; C++ std::sort is introsort and *unstable*, with std::stable_sort as the closest equivalent.
Stable insertion point: C++ std::upper_bound and Python bisect_right are library calls, while JS/TS write the binary search out — and in all three, choosing the lower bound instead silently destroys stability.
Block shifts and reversals are single C-level operations in Python (slice assignment) and C++ (std::reverse, std::copy), and explicit loops in JS/TS.
Stability has three independent chances to break — the descent test, the insertion bound, and the merge tie-break — and every language gets all three wrong in the same way if written carelessly.

Complexity

Best

O(n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

O(n + n log r) for r natural runs. Temp buffer is at most n/2. Stable, adaptive, not in-place. Comparisons are close to the information-theoretic minimum on structured data.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Default choice for sorting objects/records when the language offers it — it is what sorted(), Arrays.sort(Object[]), and JS Array.prototype.sort run.
Data with pre-existing order: appended items, concatenated sorted files, multi-key sorts done as successive stable passes.
When comparisons are expensive (complex comparators, string keys) — TimSort minimizes comparison count.

Avoid it when

Strict O(1) auxiliary memory — use Heap Sort or in-place Quick Sort / introsort.
Sorting primitives where stability is irrelevant and cache-friendly speed matters most — introsort / pdqsort / dual-pivot quick sort are faster on random data.
Fixed-width integer keys at very large n — Radix Sort is linear.
Implementing it yourself in an interview — too long; explain it and use the library.

Alternatives

Merge Sort Quick Sort Heap Sort Insertion Sort Radix Sort

Common mistakes

Treating non-strictly descending runs (5, 5, 3) as descending and reversing them — that swaps equal elements and breaks stability. Only strictly descending runs are reversed.
Assuming Java's Arrays.sort(int[]) is TimSort — for primitives it is dual-pivot quick sort; only object arrays use TimSort.
Believing it is in-place; it needs up to n/2 elements of buffer.
Writing a comparator that is not a consistent total order — TimSort detects this in Java and throws Comparison method violates its general contract!.

Interview patterns

Explain why sorted() is O(n) on already-sorted input and what "adaptive" means.
Multi-key sorting via successive stable sorts (sort by secondary key, then by primary).
Discuss stable vs unstable library sorts across languages: Python/Java-objects (TimSort, stable), C++ std::sort (introsort, unstable), std::stable_sort (merge), Go sort.Slice (pdqsort, unstable) vs sort.SliceStable.
Merge intervals / meeting rooms: rely on the library sort, then a linear sweep.

Interview questions on this