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.
| 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 a