Timsort Algorithm

The Timsort algorithm is a hybrid of insertion sort and merge sort designed for real-world data, which often contains already sorted runs. Tim Peters created it for Python in 2002, and Java uses it to sort objects. Step through a simplified version below, then read how it works.

What is Timsort?

Timsort is a hybrid of Insertion Sort and Merge Sort. It finds or creates short sorted runs, sorts them with Insertion Sort, and then merges the runs like Merge Sort. It is the default sort in Python (sorted, list.sort) and in Java for objects.

Key insight: Real-world data often contains stretches that are already sorted. Timsort detects and exploits those runs, so it reaches O(n) on already sorted input while keeping O(n log n) in the worst case. The demo and code here are a simplified version without galloping mode or run detection.

Timsort Time Complexity

Measure	Value
Best case	O(n)
Average case	O(n log n)
Worst case	O(n log n)
Space	O(n)
Stable	Yes

For a formal definition and complexity analysis, see the Tim Peters’ original design notes for Timsort, shipped in CPython’s source tree.

Algorithm Steps

1. Split the list into runs of a fixed minimum size (the demo uses 4; real Timsort uses about 32 to 64).
2. Sort each run with Insertion Sort.
3. Merge neighbouring runs into runs twice as long, using a stable merge.
4. Keep doubling the run size until a single run remains.
5. Real Timsort also detects natural runs and uses galloping to merge faster.

Advantages and Disadvantages

Advantages

• O(n) on already sorted or reverse-sorted data
• Guaranteed O(n log n) worst case
• Stable
• Excellent on real-world, partially ordered data

Disadvantages

• Needs O(n) extra memory
• Complex to implement fully (run detection, galloping, stack rules)
• Overkill for tiny lists

Real-World Applications

• Python’s built-in sorted() and list.sort()
• Java’s Arrays.sort() and Collections.sort() for objects
• Android, V8 (JavaScript Array.prototype.sort) and many other runtimes
• Sorting real-world data that is partly ordered, such as logs and time series

When to Use Timsort

In practice, call your language’s built-in sort, which is often Timsort. Implement it yourself only to learn how hybrid algorithms combine the strengths of Insertion and Merge Sort.

Timsort Implementation

Python

def insertion_range(arr, lo, hi):
    for i in range(lo + 1, hi + 1):
        key, j = arr[i], i - 1
        while j >= lo and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def merge_runs(arr, l, m, r):
    left, right = arr[l:m + 1], arr[m + 1:r + 1]
    i = j = 0
    k = l
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]; i += 1
        else:
            arr[k] = right[j]; j += 1
        k += 1
    while i < len(left):
        arr[k] = left[i]; i += 1; k += 1
    while j < len(right):
        arr[k] = right[j]; j += 1; k += 1

def timsort(arr, run=32):
    n = len(arr)
    for s in range(0, n, run):          # 1) sort small runs
        insertion_range(arr, s, min(s + run - 1, n - 1))
    size = run
    while size < n:                     # 2) merge runs
        for l in range(0, n, 2 * size):
            m = min(l + size - 1, n - 1)
            r = min(l + 2 * size - 1, n - 1)
            if m < r:
                merge_runs(arr, l, m, r)
        size *= 2
    return arr

JavaScript

function insertionRange(arr, lo, hi) {
  for (let i = lo + 1; i <= hi; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= lo && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
    arr[j + 1] = key;
  }
}

function mergeRuns(arr, l, m, r) {
  const left = arr.slice(l, m + 1), right = arr.slice(m + 1, r + 1);
  let i = 0, j = 0, k = l;
  while (i < left.length && j < right.length) {
    arr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
  }
  while (i < left.length) arr[k++] = left[i++];
  while (j < right.length) arr[k++] = right[j++];
}

function timsort(arr, run = 32) {
  const n = arr.length;
  for (let s = 0; s < n; s += run) insertionRange(arr, s, Math.min(s + run - 1, n - 1)); // 1) sort runs
  for (let size = run; size < n; size *= 2) {                                           // 2) merge runs
    for (let l = 0; l < n; l += 2 * size) {
      const m = Math.min(l + size - 1, n - 1), r = Math.min(l + 2 * size - 1, n - 1);
      if (m < r) mergeRuns(arr, l, m, r);
    }
  }
  return arr;
}

FAQ

Who invented Timsort and where is it used?

Tim Peters wrote it for Python’s list.sort() in 2002. Java adopted it for sorting objects (Arrays.sort on object arrays and Collections.sort), and Android and V8 (JavaScript in Chrome) have used it too. Python 3.11 kept Timsort’s design but switched its merge-ordering rule to Powersort.

Why is Timsort O(n) on sorted data?

It first scans for runs that are already in order. A fully sorted list is one long run, so after a single pass there is nothing left to merge.

What is minrun?

The minimum run length. Short natural runs are extended to minrun (typically 32 to 64 elements in real implementations; 4 in this demo) with Insertion Sort, which is fast on small inputs, before the runs are merged pairwise as in Merge Sort.

---

More Sorting Algorithms

• Merge Sort
• Insertion Sort
• Quick Sort
• Heap Sort