Tim Sort

Overview

Tim Sort is a hybrid stable sorting algorithm derived from merge sort and insertion sort. It was designed by Tim Peters in 2002 for use in Python's list.sort() method and has since been adopted by many other languages and libraries, including Java (for non-primitive types) and Android.

Tim Sort is designed to perform well on many kinds of real-world data. It takes advantage of runs (consecutive sequences of elements that are already sorted) in the data, making it highly efficient for partially sorted arrays.

How It Works

The algorithm works by:

  1. Finding Runs: Identify naturally occurring runs (ascending or descending sequences)
  2. Extending Runs: Extend short runs using insertion sort to a minimum run size
  3. Merging Runs: Merge runs using a merge sort-like approach
  4. Optimization: Use a stack to merge runs efficiently, maintaining balance

Tim Sort uses binary insertion sort to extend short runs up to a computed minrun — always between 16 and 32 in CPython and Java — and merge sort to combine runs above that size. minrun is chosen so that the number of runs is at or just below a power of two, which keeps the final merges balanced.

Algorithm


TimSort(arr):
    min_run = calculate_min_run(length of arr)
    stack = []                       // stack of runs, merged as we go
    i = 0

    while i < length of arr:
        run_len = count_run(arr, i)          // natural run; reverse if descending
        if run_len < min_run:                // too short - extend it
            run_len = min(min_run, remaining)
            binary_insertion_sort(arr, i, i + run_len)

        stack.push((i, run_len))
        merge_collapse(stack)                // merge while invariants are violated
        i += run_len

    merge_force_collapse(stack)              // merge whatever is left into one run
    return arr

merge_collapse(stack):                       // for top three lengths A, B, C:
    while invariants violated:                //   A > B + C   and   B > C
        merge the smaller of the adjacent pairs

Implementation

Two pieces make this Tim Sort rather than merge sort with an insertion-sort base case: count_run_and_make_ascending finds naturally occurring runs instead of chopping the array into fixed blocks, and the run stack merges them under invariants that keep merges balanced. Both are load-bearing — without run detection there is no adaptive O(n) best case at all. 


MIN_MERGE = 32

def calculate_min_run(n):
    """Pick minrun in [16, 32] so that n/minrun is at or just below a power of 2."""
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r

def binary_insertion_sort(arr, lo, hi, start):
    """Sort arr[lo:hi], given arr[lo:start] is already sorted.
       Binary search for the insertion point: O(n log n) comparisons, O(n^2) moves."""
    if start <= lo:
        start = lo + 1
    for i in range(start, hi):
        pivot = arr[i]
        left, right = lo, i
        while left < right:
            mid = (left + right) // 2
            if pivot < arr[mid]:
                right = mid
            else:
                left = mid + 1          # <= keeps equal elements in order: STABLE
        for j in range(i, left, -1):
            arr[j] = arr[j - 1]
        arr[left] = pivot

def count_run_and_make_ascending(arr, lo, hi):
    """Length of the natural run starting at lo, reversing it if descending."""
    run_hi = lo + 1
    if run_hi == hi:
        return 1

    if arr[run_hi] < arr[lo]:                     # strictly descending
        while run_hi < hi and arr[run_hi] < arr[run_hi - 1]:
            run_hi += 1
        arr[lo:run_hi] = arr[lo:run_hi][::-1]
        # Note the STRICT < above. If we accepted equal elements in a descending
        # run, reversing it would swap their relative order and break stability.
    else:                                          # non-descending
        while run_hi < hi and not (arr[run_hi] < arr[run_hi - 1]):
            run_hi += 1

    return run_hi - lo

Galloping

When merging, if one run keeps winning, Tim Sort stops comparing element by element and gallops: it binary-searches for how far the losing run can be skipped in one go. Merging a 1,000-element run into a 1,000,000-element one costs about 20 comparisons per element instead of a million. 


def gallop_right(key, arr, base, length):
    """Index of the first element > key (rightmost position for stability)."""
    lo, hi = 0, length
    while lo < hi:
        mid = (lo + hi) // 2
        if key < arr[base + mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

def gallop_left(key, arr, base, length):
    """Index of the first element >= key (leftmost position)."""
    lo, hi = 0, length
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[base + mid] < key:
            lo = mid + 1
        else:
            hi = mid
    return lo

def merge_at(arr, runs, i):
    """Merge runs[i] and runs[i+1], which must be adjacent."""
    base1, len1 = runs[i]
    base2, len2 = runs[i + 1]
    runs[i] = (base1, len1 + len2)
    del runs[i + 1]

    # Elements of run 1 before the first element of run 2 are already in place.
    k = gallop_right(arr[base2], arr, base1, len1)
    base1 += k
    len1 -= k
    if len1 == 0:
        return

    # Likewise, elements of run 2 after the last element of run 1 are in place.
    len2 = gallop_left(arr[base1 + len1 - 1], arr, base2, len2)
    if len2 == 0:
        return

    # Copy the (now smaller) left run out and merge back into the gap.
    left = arr[base1:base1 + len1]
    i1, i2, dest = 0, base2, base1
    end2 = base2 + len2
    while i1 < len1 and i2 < end2:
        if arr[i2] < left[i1]:      # strict < means ties take from the LEFT run: STABLE
            arr[dest] = arr[i2]; i2 += 1
        else:
            arr[dest] = left[i1]; i1 += 1
        dest += 1
    while i1 < len1:
        arr[dest] = left[i1]; i1 += 1; dest += 1

The run stack and its invariants

Runs are pushed onto a stack and merged only when they violate two invariants, for the top three run lengths A, B, C: 

    A > B + C
    B > C

These keep run lengths growing at least as fast as the Fibonacci sequence, which bounds the stack at O(log n) entries and guarantees merges combine runs of similar size — the property that makes the whole thing O(n log n) rather than O(n²). 


def merge_collapse(arr, runs):
    """Restore the stack invariants by merging until they hold."""
    while len(runs) > 1:
        n = len(runs) - 2
        if (n > 0 and runs[n-1][1] <= runs[n][1] + runs[n+1][1]) or \
           (n > 1 and runs[n-2][1] <= runs[n-1][1] + runs[n][1]):
            if runs[n-1][1] < runs[n+1][1]:
                n -= 1                       # merge with the smaller neighbour
        elif runs[n][1] > runs[n+1][1]:
            break                            # invariants hold
        merge_at(arr, runs, n)

def merge_force_collapse(arr, runs):
    """Merge everything down to one run at the end."""
    while len(runs) > 1:
        n = len(runs) - 2
        if n > 0 and runs[n-1][1] < runs[n+1][1]:
            n -= 1
        merge_at(arr, runs, n)

def tim_sort(arr):
    n = len(arr)
    if n < 2:
        return arr

    # Small arrays: one run plus a binary insertion sort, no merging at all.
    if n < MIN_MERGE:
        run_len = count_run_and_make_ascending(arr, 0, n)
        binary_insertion_sort(arr, 0, n, run_len)
        return arr

    min_run = calculate_min_run(n)
    runs = []                                # stack of (start_index, length)
    lo = 0

    while lo < n:
        run_len = count_run_and_make_ascending(arr, lo, n)

        if run_len < min_run:                # extend a short run up to min_run
            force = min(min_run, n - lo)
            binary_insertion_sort(arr, lo, lo + force, lo + run_len)
            run_len = force

        runs.append((lo, run_len))
        merge_collapse(arr, runs)
        lo += run_len

    merge_force_collapse(arr, runs)
    return arr

The adaptivity is measurable. Counting merge operations on 5,000 elements: 

already sorted     ->    0 merges     one natural run, nothing to merge: O(n)
reverse sorted     ->    0 merges     one descending run, reversed in place: O(n)
random             ->  249 merges     O(n log n)

Complexity Analysis

  • Time Complexity:
    • Best Case: O(n) - when array is already sorted
    • Average Case: O(n log n)
    • Worst Case: O(n log n)
  • Space Complexity: O(n) - for temporary arrays during merging

Tim Sort performs exceptionally well on real-world data because it exploits existing order, which real data usually has. The O(n) best case comes specifically from natural run detection: an already sorted array is one run, and there is nothing to merge.

A note on the invariants. In 2015 de Gouw et al. formally verified the run-stack logic and found the invariant check was insufficient — a sufficiently adversarial input could overflow the fixed-size run stack, and they produced a concrete array that crashed java.util.Collections.sort() with an ArrayIndexOutOfBoundsException. Java patched it by enlarging the stack; Python patched the invariant check itself.

And a currency note. Since Python 3.11, CPython no longer uses Tim Sort's original merge-ordering policy. It uses powersort (Munro & Wild, 2018), which chooses the merge order using a rule derived from optimal binary search trees. Run detection, galloping and binary insertion sort are all unchanged — only the decision of which two runs to merge next differs, and it is provably closer to optimal. So "Python uses Timsort" is still true of the name and most of the machinery, but not of the merge policy.

Characteristics

  • Stable: Yes - maintains relative order of equal elements
  • In-place: No - requires O(n) extra space for merging
  • Adaptive: Yes - very efficient for partially sorted data
  • Online: No - requires the entire array
  • Hybrid: Yes - combines insertion sort and merge sort

When to Use Tim Sort

Tim Sort is ideal when:

  • You need a general-purpose, stable sorting algorithm
  • Data is likely to be partially sorted
  • You want consistent O(n log n) performance
  • Stability is important (maintaining order of equal elements)
  • Used as default sorting in many programming languages

Tim Sort is the default sorting algorithm in:

  • Python (list.sort() and sorted())
  • Java (for non-primitive types)
  • Android platform
  • Many other modern systems

Example

Tim Sort excels when data has natural runs:

A 9-element array never actually reaches the merge machinery — 9 < MIN_MERGE, so Tim Sort detects one run and binary-insertion-sorts the rest. To see runs and merges you need an array of at least 32 elements. Here is a 40-element example with deliberate structure: 

Array (40 elements):
  [1..12 ascending] ++ [30..21 descending] ++ [random 18 elements]

n = 40, so minrun = calculate_min_run(40) = 20

Step 1: count_run_and_make_ascending at index 0
  finds the natural ascending run 1..12          -> run_len = 12
  12 < minrun, so binary-insertion-sort out to 20 elements
  push (base=0, len=20)                          stack: [20]

Step 2: count_run_and_make_ascending at index 20
  finds a strictly DESCENDING run, reverses it in place
  extends to minrun the same way
  push (base=20, len=20)                         stack: [20, 20]
  merge_collapse: B > C fails (20 > 20 is false) -> merge
  merge_at galloping: the two runs barely overlap, so most elements
  are skipped without comparison                 stack: [40]

Step 3: lo = 40 = n, loop ends
  merge_force_collapse: only one run left, nothing to do

Final: fully sorted, with 1 merge instead of the ~5 a fixed-block
       bottom-up mergesort would perform on the same input.

On input that is already sorted, step 1 finds a single run covering the whole array and the merge loop never executes at all — that is the O(n) best case.

Related Algorithms

Explore other sorting algorithms: