Tim Sort

Tim sort is a stable, adaptive, hybrid sorting algorithm designed by Tim Peters in 2002 for use as Python’s built-in list.sort() and sorted(). It combines the worst-case guarantees of Merge Sort with the small-array efficiency of Insertion Sort, plus a clever “run-detection” optimization that recognizes already-sorted (or reverse-sorted) subsequences in the input and uses them as merge units instead of starting from singletons. The result is O(n log n) worst-case time, O(n) time on already-sorted input, full stability, and excellent practical performance on real-world data — which is rarely uniform random and almost always contains long runs of structured order. Today, Tim sort is the default sort() implementation in Python (CPython), Java (for Object[], since JDK 7), Android, Octave, V8 (Chrome’s JavaScript engine) since 2018, and Swift’s stdlib, making it arguably the most-executed sorting algorithm on Earth.

1. Intuition — Sorting Mail by Hand

Imagine sorting a stack of mail by date.

• You fan it out and notice that big chunks are already in date order — perhaps a batch of bills from one company, then a batch of magazines, all roughly chronological within each batch. Other parts are scrambled.
• A naive algorithm would ignore this structure and treat every letter as if it had to be re-sorted from scratch. Tim sort doesn’t.
• Tim sort scans through the input identifying “natural runs” — maximal subsequences that are already monotonic (either ascending or strictly descending). A descending run can be reversed in place to make it ascending, costing only O(length). Now you have a sequence of sorted runs.
• It then merges adjacent runs using a Merge Sort-style merge. But it doesn’t blindly merge in input order — it uses a stack-based scheduling discipline that keeps merge-balance favorable, so total merging stays O(n log n).
• Short runs are extended to a minimum length by Insertion Sort before merging, because tiny merges have bad constant-factor overhead.
• For specific merge patterns where one run dominates the other in a known way, it uses galloping mode — exponential search to skip past long runs of “the other side wins” without doing per-element comparisons.

The big idea: real-world data has structure. Exploit the structure instead of shuffling it back into a uniform-random representation just to apply a textbook algorithm. On uniform-random input, Tim sort is no better than merge sort. On real input — log files, partially sorted lists, concatenations of sorted lists, slightly-perturbed sorted lists — Tim sort can be dramatically faster.

2. Tiny Worked Example (n = 12)

Sort [5, 7, 9, 1, 4, 2, 3, 6, 8, 10, 11, 0].

Step 1: Identify natural runs (left to right)

Walk the array, identifying maximal monotonic subsequences. A run is maximal — extend it as long as possible.

[5, 7, 9 | 1, 4 | 2 | 3, 6, 8, 10, 11 | 0]
  ↑──────  ↑───  ↑   ↑──────────────   ↑
  ascending asc  1   ascending          1
  length 3  len2  el  length 5          el

For this example all runs happen to be ascending. If a run had been strictly descending (e.g. [9, 7, 5]), Tim sort would reverse it in place to [5, 7, 9] — flipping a strictly-descending run is stable; flipping a non-strictly-descending one (with equal elements) is not stable, so the rule is strictly descending only. (This stability subtlety is one reason the spec uses < not <=.)

Step 2: Determine min_run and extend short runs with insertion sort

For n = 12, Tim sort would compute a min_run value (typically in [32, 64] for large n; this tiny example would just use n directly, but to illustrate, suppose min_run = 4).

Each natural run shorter than min_run is extended by selecting the next min_run - len elements and using binary insertion sort to merge them into the current run.

So [1, 4] (length 2) might be extended by 2 more elements to length 4 via insertion sort. Similarly the singleton [2] would be extended.

In real Tim sort on real data, this step ensures no run going into the merge tree is shorter than min_run, which keeps the merge tree balanced (next step).

Step 3: Merge runs using a stack with invariants

Tim sort maintains a stack of pending runs. As each new run is identified (and extended), it is pushed onto the stack. After every push, the algorithm checks the top three runs A (third-from-top), B (second-from-top), C (top), and enforces two invariants:

1. |A| > |B| + |C|
2. |B| > |C|

If either is violated, the algorithm merges B with the smaller of A and C, and re-checks. This is repeated until the invariants hold.

The invariants ensure that runs being merged are roughly the same size, which is what gives merge sort its O(n log n) worst-case bound: each element participates in O(log n) merges. Without the invariants, you might end up merging a tiny run into a huge one repeatedly, giving O(n²) work.

Step 4: When the input is exhausted, force-merge the entire stack

After the input is fully consumed, the stack still contains a few merged-but-not-finalized runs. They are merged top-down until one sorted run remains: the output.

For our example, the merging would proceed in stack-balanced order, ending with a single sorted run [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

(The detailed step-by-step stack mutations for a tiny example are pedagogically clarifying but verbose; the key conceptual point is identify-runs → extend → push-and-balance-merge → force-merge.)

3. Pseudocode

tim_sort(arr):
    n := length(arr)
    if n < 64:
        binary_insertion_sort(arr, 0, n)             # small array: just insertion sort
        return
    min_run := compute_min_run(n)                    # in [32, 64]
    stack := empty                                    # stack of pending runs (start, length)
    i := 0
    while i < n:
        # 1. Identify the next natural run starting at i
        run_start := i
        if i + 1 == n:
            i := i + 1
        elif arr[i] <= arr[i+1]:
            # Ascending run: extend while non-decreasing
            while i + 1 < n and arr[i] <= arr[i+1]:
                i := i + 1
            i := i + 1
        else:
            # Strictly descending run: extend while strictly decreasing, then reverse
            while i + 1 < n and arr[i] > arr[i+1]:
                i := i + 1
            i := i + 1
            reverse(arr, run_start, i)
        run_length := i - run_start
        # 2. Extend short runs to min_run by binary insertion sort
        if run_length < min_run:
            extend_len := min(min_run, n - run_start)
            binary_insertion_sort(arr, run_start, run_start + extend_len, sorted_prefix=run_length)
            run_length := extend_len
            i := run_start + run_length
        # 3. Push run onto stack and merge to maintain invariants
        push(stack, (run_start, run_length))
        merge_collapse(stack, arr)
    # 4. Force-merge remaining runs into one
    merge_force_collapse(stack, arr)

merge_collapse(stack, arr):
    while length(stack) > 1:
        n := length(stack)
        if (n >= 3 and stack[-3].len <= stack[-2].len + stack[-1].len)
           or (n >= 4 and stack[-4].len <= stack[-3].len + stack[-2].len):
            # Merge stack[-2] with smaller of stack[-3], stack[-1]
            if stack[-3].len < stack[-1].len:
                merge_at(stack, arr, n - 3)
            else:
                merge_at(stack, arr, n - 2)
        elif stack[-2].len <= stack[-1].len:
            merge_at(stack, arr, n - 2)
        else:
            break

compute_min_run(n):
    # Pick min_run in [32, 64] such that n / min_run is just less than a power of 2
    r := 0
    while n >= 64:
        r := r | (n & 1)
        n := n >> 1
    return n + r

The compute_min_run routine ensures the number of runs is close to a power of 2, which makes the merge tree perfectly balanced — minimizing total merge work.

4. Python Implementation

CPython’s actual Tim sort is ~1500 lines of optimized C in Objects/listobject.c. A faithful Python demonstration of the core algorithm:

MIN_MERGE = 32
 
def compute_min_run(n: int) -> int:
    """Pick min_run in [32, 64] so n/min_run is just under a power of 2."""
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r
 
def insertion_sort(arr, lo, hi):
    """In-place insertion sort on arr[lo:hi]."""
    for i in range(lo + 1, hi):
        key = arr[i]
        j = i - 1
        while j >= lo and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
 
def merge(arr, lo, mid, hi):
    """Merge sorted arr[lo:mid] and arr[mid:hi]."""
    left = arr[lo:mid]
    right = arr[mid:hi]
    i = j = 0
    k = lo
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:           # <= for stability
            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 tim_sort(arr):
    n = len(arr)
    if n < 2:
        return
    min_run = compute_min_run(n)
    # Sort each min_run-sized chunk with insertion sort
    for start in range(0, n, min_run):
        end = min(start + min_run, n)
        insertion_sort(arr, start, end)
    # Iteratively merge size-2*min_run, 4*min_run, ... runs
    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)
            if mid < right:
                merge(arr, left, mid, right)
        size *= 2

This is a simplified Tim sort that omits run-detection (it just chops the array into fixed min_run chunks) and the stack-with-invariants merge scheduling (it does pure bottom-up merges). It demonstrates the insertion-sort-base + merge-sort-up structure but misses the “exploit natural runs” cleverness that gives real Tim sort its O(n) best case. A faithful implementation needs ~200–400 lines of Python; the canonical reference is Tim Peters’s timsort.txt design notes attached to the original 2002 announcement.

5. Complexity

5.1 Time

Best case: O(n). Already-sorted (or already-reverse-sorted) input. Run detection identifies the entire array as one ascending run; no insertion sort or merging is needed; the algorithm terminates after one linear scan.

Worst case: O(n log n). Established by Auger, Jugé, Nicaud & Pivoteau (2018) “On the Worst-Case Complexity of TimSort” (ESA 2018). The exact constant is around 3 n log₂ n + O(n) comparisons in the worst case, which is competitive with classical merge sort.

Why this matches the comparison-sort lower bound Ω(n log n). Any comparison-based sort can be modeled as a decision tree with n! leaves (one per input permutation); the tree’s depth is at least ⌈log₂(n!)⌉ = Θ(n log n). Tim sort hits this bound up to a constant factor. Like Merge Sort and Heap Sort, it is asymptotically optimal among comparison sorts.

Average case on real-world data. Tim sort’s killer feature is that “real data is not random.” Logs are mostly time-ordered; user-uploaded lists are often pre-sorted; concatenations of sorted lists are common in databases. On such inputs, Tim sort approaches O(n) while Quicksort and Merge Sort still pay O(n log n). Empirical benchmarks routinely show Tim sort 2–10× faster than naive merge sort on partially-sorted real-world data.

5.2 Space

• Auxiliary: O(n) in the worst case — the merge step needs a temporary buffer of up to n/2 elements.
• Stack: O(log n) for the run stack.
• Total auxiliary: O(n).

This is the same as classical Merge Sort — Tim sort does not improve on merge sort’s space bound, only its constant-factor time on structured input. (For memory-constrained settings, Heap Sort or Quicksort are better choices.)

5.3 The 2015 OpenJDK Bug Story

A delightful footnote on Tim sort’s complexity: in 2015, de Gouw et al. (CAV 2015) “OpenJDK’s java.utils.Collection.sort() Is Broken” used formal-methods tools (KeY) to prove that Tim sort’s run-stack invariant condition was too weak and could be violated, causing the stack to overflow on adversarially-crafted inputs of around 65 million elements. The paper provided a correct invariant. OpenJDK, Python, and Android all subsequently fixed their implementations. This is one of the rare examples of formal verification finding a real bug in a widely-deployed standard-library algorithm. It also illustrates that “obviously correct” merge-stack invariants can be subtly wrong even after years of production use.

6. The Three Big Ideas

6.1 Natural Run Detection

Real-world arrays are rarely uniform-random. A scan through the input identifies maximal monotonic subsequences (runs), which serve as the merge sort’s pre-sorted starting units. On already-sorted input, the entire array is one run; no work is needed beyond the scan. This is the source of Tim sort’s adaptiveness.

To preserve stability, only strictly descending runs are reverse-flipped. Non-strictly descending runs (with equal elements) cannot be flipped without breaking stability. So a run like [5, 5, 5, 4, 3] is not a “descending run” in Tim sort’s sense — Tim sort would identify just [5] and continue.

6.2 min_run and Insertion-Sort Run Extension

Pure merge sort starts with size-1 runs and merges upward, so the merge tree has log₂ n levels. Tim sort’s run detection sometimes finds tiny natural runs (length 1 or 2). Merging these directly is wasteful — the per-merge overhead dominates.

So Tim sort enforces a minimum run length min_run, computed in the range [32, 64] based on n such that n / min_run is just below a power of 2 (giving a perfectly balanced merge tree). Any natural run shorter than min_run is extended by binary insertion sort: take the next few elements after the run and insertion-sort them into the run’s tail.

The exact min_run formula is compute_min_run(n): keep stripping low bits until n < 64, OR’ing the stripped bits back in. This produces 32 ≤ min_run ≤ 64 such that the number of full runs is close to a power of 2 — minimizing wasted merge work at the top of the tree.

6.3 Galloping Mode

When merging two sorted runs A and B, the standard merge does one comparison per element popped. If A is much smaller than B, you might end up taking many consecutive elements from B while A’s next element waits — each requiring a wasted “is A’s head smaller?” comparison.

Tim sort’s galloping mode kicks in after a threshold (MIN_GALLOP = 7, adjustable) of consecutive wins by one side. Instead of doing per-element comparisons, it uses exponential search (also called galloping search) to find how many of B’s elements are less than A’s head — doubling the search distance each step until it overshoots, then binary-searching the final gap. This finds the boundary in O(log k) comparisons instead of O(k).

Galloping is then turned off automatically if it’s not paying off. The mode is self-tuning.

This is essentially the algorithm exploiting the correlation between input keys: if one side has been winning a lot, it’s likely to keep winning, so let’s do exponential search instead of linear.

7. Stability

Tim sort is stable. Stability is preserved by:

1. The merge step using <= (left wins ties): if left[i] <= right[j].
2. Run detection treating only strictly descending sequences as descending (so reversal never reorders equal elements).
3. Binary insertion sort’s stability guarantee (uses strict > in the slide condition).

This is critical for Python and Java users because stability is documented behavior of sorted() / list.sort() / Arrays.sort() for Object arrays — code in the wild depends on it. Switching to a non-stable sort would break programs that sort by secondary key first, then primary, expecting equal-primary elements to retain secondary order.

8. Tim Sort vs Other Sorts

Property	Tim Sort	Merge Sort	Quicksort	Heap Sort	Insertion Sort
Worst time	O(n log n)	O(n log n)	O(n²)	O(n log n)	O(n²)
Average time	O(n log n)	O(n log n)	O(n log n)	O(n log n)	O(n²)
Best time	O(n) (sorted input)	O(n log n)	O(n log n)	O(n log n)	O(n)
Space	O(n)	O(n)	O(log n) stack	O(1)	O(1)
Stable?	✅	✅	❌	❌	✅
Adaptive?	✅	❌	❌	❌	✅
In-place?	❌	❌	✅	✅	✅
Used by	Python, Java (Object[]), V8, Swift, Android	Java pre-7 (Object[])	C qsort, Intro Sort base	Intro Sort fallback, embedded	Hybrid base case

Tim sort is the right choice when all of:

• Stability matters (sorting structured records by key).
• Real-world data has structure you can exploit.
• Memory for the merge buffer is available.

Tim sort is not the right choice when:

• Memory is tight — use Heap Sort or Quicksort (O(1) / O(log n) space).
• Input is adversarial / uniform random — Quicksort is faster constants-wise.
• Stability doesn’t matter and you want maximum throughput on random data — Intro Sort (quicksort + heapsort fallback + insertion-sort base case).

This is exactly why C++ std::sort (which doesn’t promise stability) uses Intro Sort, while Python and Java (which do promise stability) use Tim sort — different stability constraints, different best algorithm.

9. Pitfalls

9.1 Worst-Case Adversarial Input Can Be Crafted

While O(n log n) is the proven worst case, adversaries can construct inputs that force Tim sort into close to its worst-case time. For non-adversarial workloads this doesn’t matter; for cryptographic / security-sensitive sorts, consider Heap Sort (which has identical worst and best case, providing constant-time guarantees).

9.2 Memory Allocation in the Merge Step

Tim sort’s merge uses a temporary buffer of up to n / 2 elements. On memory-constrained devices, this can OOM. Most production implementations grow the buffer lazily as needed, but it’s still O(n) worst case. The buffer is typically reused across merges within one sort call.

9.3 The “Strictly Descending” Subtlety

If you implement Tim sort yourself and use >= instead of > for descending-run detection, your sort silently becomes unstable. The bug only shows up on inputs with equal elements. Easy to miss in testing.

9.4 Computed min_run is Not Always 32

Many introductions say min_run = 32, but it’s computed in the range [32, 64] based on n. A common bug in “from-scratch” implementations is hardcoding 32, which can hurt performance on inputs whose length doesn’t play nicely with merge tree balance.

9.5 The 2015 Stack-Invariant Bug

If you write your own Tim sort and use the original (pre-2015) merge stack invariant, your sort can crash on inputs of ~65 million elements. Use the corrected invariant from de Gouw et al. (CAV 2015). The fix is to add a check for the fourth-from-top run in the invariant (compare stack[-4].len <= stack[-3].len + stack[-2].len), not just the top three.

9.6 Galloping Threshold Tuning

MIN_GALLOP = 7 is the default; production implementations adapt it dynamically — increasing it when galloping doesn’t help, decreasing it when it does. Hard-coding 7 in your reimplementation will work but be slightly suboptimal.

10. Diagram — The Tim Sort Pipeline

flowchart TD
    Input[("Input array")] --> Scan["Scan for natural runs<br/>(ascending or strictly descending)"]
    Scan --> Reverse["Reverse strictly-descending runs<br/>in place (O(length))"]
    Reverse --> Extend{"Run length < min_run?"}
    Extend -- yes --> Insertion["Binary insertion sort<br/>extends run to min_run"]
    Extend -- no --> Push["Push run onto stack"]
    Insertion --> Push
    Push --> Invariant{"Stack invariants<br/>satisfied?"}
    Invariant -- no --> Merge["merge_at(): merge two<br/>adjacent runs (with galloping)"]
    Merge --> Invariant
    Invariant -- yes --> More{"More input?"}
    More -- yes --> Scan
    More -- no --> Force["Force-merge entire stack<br/>top-to-bottom"]
    Force --> Output[("Sorted output")]

What this diagram shows. The full Tim sort control flow. The input is consumed left-to-right, one natural run at a time. Each run is normalized (reversed if descending), extended to min_run if too short, and pushed onto a stack of pending runs. After each push, stack invariants (the merge-balance conditions) are checked; violations trigger merges of adjacent stack-top runs (using galloping where profitable). When input is exhausted, the remaining stack is force-merged to a single run. The diagram makes clear that Tim sort’s structure is fundamentally a streaming merge sort that works opportunistically on whatever runs the input provides, with insertion sort as the small-block tool and a stack discipline keeping merges balanced. The two key efficiency wins — adaptiveness and galloping — show up in the “Reverse”/“Extend” step (capturing input structure cheaply) and the “Merge” step (skipping wasted comparisons during one-sided merges).

11. Common Interview Problems

Problem	Tim Sort Connection
”What sort does Python’s sorted() use?”	Tim sort. Bonus: same for Java’s Arrays.sort on Object[].
”Why is sorted() so fast on a list that’s already mostly sorted?”	Adaptiveness — Tim sort detects natural runs and avoids re-sorting them.
”Sort a list of (name, age) tuples by age, then by name within equal ages”	Stability lets you sort by name first, then by age — Tim sort preserves the name-order within equal-age groups.
”Sort the result of merging k sorted streams”	The merged stream is one sorted run; Tim sort sorts it in O(n).
”Why does V8 (Chrome’s JS engine) sort behavior differ from Firefox?”	V8 switched to Tim sort in 2018 (V8 7.0); pre-2018 it used unstable quicksort, leading to subtle behavior differences.

12. Open Questions

• How does Powersort (Munro & Wild 2018), a Tim-sort-like algorithm with provably optimal merge tree based on nearest-larger-value heuristics, compare in practice? It has been integrated into CPython 3.11+ as the merge policy.
• Are there workloads (cryptographic, real-time) where Tim sort’s variance is unacceptable and a non-adaptive sort like Heap Sort is preferred?
• Could galloping be made more aggressive (lower threshold) for very long runs, or does the current adaptive MIN_GALLOP already converge to the optimum?

13. See Also

• Merge Sort — Tim sort’s core merge engine
• Insertion Sort — Tim sort’s small-block (and run-extension) sort
• Quicksort — alternative for unstable in-place sorting
• Heap Sort — alternative for O(1)-space worst-case-bounded sorting
• Intro Sort — the non-stable hybrid analog (quicksort + heap sort + insertion sort)
• Counting Sort — non-comparison sort for bounded-integer keys
• Big-O Notation
• SWE Interview Preparation MOC