Real-world data is rarely random — it comes in already-sorted stretches. Timsort, the default sort in Python and Java, is built to exploit exactly that. It scans for natural runs (maximal ascending or descending stretches, descending ones reversed), pads short runs up to a minimum length with a quick insertion sort, and then merges the runs together using a stack that keeps merges balanced (with a “galloping” fast-path when one run is consistently smaller). The payoff: already-sorted or nearly-sorted input sorts in close to O(n), while worst-case stays O(n log n) and the sort is stable. Watch the runs get found and merged.
A maximal already-sorted stretch (ascending, or descending then reversed).
minrun
A minimum run length (~32–64); short runs are extended with insertion sort.
merge
Combine two sorted runs into one, stably, like the merge step of merge sort.
galloping
A fast-path merge that binary-jumps when one run keeps winning.
timsort.js — find runs, then merge them
Ready
An array with some existing order. First we detect the natural runs — stretches already sorted. Then we merge adjacent runs into longer sorted ones until the whole array is sorted. Step to begin.
–
runs
0
merges
detect
phase
How it works
Timsort’s speed comes from not throwing away the order the data already has. A purely divide-and-conquer sort ignores that a chunk of the input might already be sorted; Timsort actively looks for those chunks. It walks the array once, identifying each maximal run — if a stretch is descending, it’s reversed in place (which keeps the sort stable). Runs shorter than minrun are grown to that length with binary insertion sort, which is very fast on tiny, nearly-sorted arrays. Then the runs are merged in a disciplined order: a stack of pending runs is kept, and merges are triggered to maintain size invariants so that no merge is wildly unbalanced. On data that arrives in a few long runs, there’s almost nothing to do — hence the near-linear best case — while random data still degrades gracefully to O(n log n).
1
Find natural runs
Scan left to right for maximal sorted stretches. Ascending runs are kept; a descending run is reversed in place so it becomes ascending — done stably.
2
Extend short runs (insertion sort)
If a run is shorter than minrun (~32–64), extend it to that length using binary insertion sort, which is fast on small, nearly-ordered pieces.
3
Merge runs on a stack
Push runs onto a stack and merge adjacent ones to keep their sizes balanced (roughly Fibonacci-like invariants), so merges are efficient. Galloping speeds up merges when one run consistently wins.
✓
Adaptive and stable
Nearly-sorted input has few, long runs → almost no work (~O(n)). Random input still merges in O(n log n). Equal elements keep their original order, so the sort is stable.
Worst case
O(n log n)
Nearly-sorted
~O(n)
Stable
Yes
Default in
Python, Java
The code
# Timsort, conceptually: detect runs, extend, mergedef timsort(a):
minrun = compute_minrun(len(a)) # ~32-64
runs = []
i = 0
while i < len(a):
run_end = find_run(a, i) # maximal sorted stretchif descending(a, i, run_end): reverse(a, i, run_end)
if run_end - i < minrun: # pad short runs
run_end = min(i + minrun, len(a))
binary_insertion_sort(a, i, run_end)
runs.append((i, run_end)); i = run_end
return merge_runs_with_stack(a, runs) # balanced, galloping merges
Quick check
1. What does Timsort look for to go fast on real data?
Timsort scans for runs: maximal already-sorted stretches (ascending, or descending which it reverses). Real data has many such runs, and exploiting them is what makes Timsort near-linear on nearly-sorted input.
2. What is Timsort’s time complexity?
Timsort is O(n log n) in the worst case like merge sort, but adaptive: when the data already contains long runs, there is little merging to do, so it approaches O(n).
3. Why is Timsort described as stable?
A stable sort preserves the relative order of equal elements. Timsort’s merge (favoring the left run on ties) and its careful run handling maintain that order, which is why it’s the default where stability matters, like Python’s sort.
FAQ
What is Timsort?
A hybrid, stable, adaptive sort (Tim Peters, 2002) combining merge sort and insertion sort. It finds natural sorted runs, extends short ones with insertion sort, and merges them with a balancing stack and galloping. O(n log n) worst case, ~O(n) on nearly-sorted input; the default sort in Python and Java.
Why is Timsort so fast on real-world data?
Real data often has long already-sorted stretches. Timsort detects these runs and only merges them, so a handful of long runs means very little work — approaching linear time. A sort that ignores existing order does the same work regardless of how sorted the input already is.
What is galloping mode?
When merging two runs, if one keeps winning, Timsort switches to galloping: it uses exponential/binary search to jump ahead and copy a whole block from the winning run at once, instead of element-by-element. It reverts to normal merging when the runs interleave evenly.
How does Timsort compare to quicksort?
Quicksort is usually faster on random primitive arrays and sorts in place, but is unstable with an O(n²) worst case. Timsort is stable, adaptive (much faster on partially-sorted data), and guaranteed O(n log n), using O(n) extra memory. Languages often use Timsort for object sorts and quicksort for primitives.