Timsort

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Timsort

Loading interactive demo…

Timsort finds the runs the data already has (ascending ones as they are, descending ones reversed in place), extends short runs with binary insertion sort up to minrun, and merges runs off a stack whose size rules keep the merges balanced. Translucent bars are copies waiting in the merge buffer. Take the tour, or press and explore. Legend:

The panel beside the stage is the real Timsort class from the published library executing in your browser, with the current line highlighted.

The key being inserted into a short run, or the left run's front bar during a merge (always the brightest bar).
The bar compared against it: the binary-search probe, or the right run's front. The bracket points at the pair.
The left run of the pair being merged.
The right run of the pair being merged.
The run, or the merged range, completed so far.
Every bar, once the whole array is sorted.

The library sets minMerge to 8 instead of CPython's 64 so several runs stay visible at these sizes. Drag the bars into a few sorted stretches and watch the probes and merges fall away.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Timsort is a merge sort that refuses to start from single elements. The run finder costs $O(n)$ once and hands back runs of length at least $\text{minrun}$ (about $n / 2^k$ for the largest $k$ that keeps it under $\text{minMerge}$ ), so there are at most

r \le \frac{n}{\text{minrun}} \approx 2^k

runs to merge. Extending a run by binary insertion spends $O(\log \text{minrun})$ comparisons per element but shifts up to $\text{minrun}$ slots per insert, a constant-bounded cost while $\text{minrun}$ is small. The stack invariants (each run longer than the next, and longer than the next two combined) force run lengths to grow at least as fast as Fibonacci numbers, so the stack is $O(\log n)$ deep and every element takes part in $O(\log r)$ merges: $O(n \log n)$ in the worst case, matching merge sort. The payoff is the other end: an already sorted or reversed array is a single run, $n - 1$ comparisons and zero merges, so the best case is $O(n)$ , and any input made of a few long runs sits close to it. Timsort is stable (ties go to the left run, and only strictly descending runs are reversed) and not in place: the merge buffer holds a copy of the left run, $O(n)$ extra in the worst case, plus the run stack.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

minRun is CPython's loop verbatim: shift n right until it fits under minMerge, remembering whether any dropped bit was set, so n / minrun lands on or just below a power of two and the final merges stay balanced. minMerge is 8 here against CPython's 64, purely so several runs stay visible on the stage.
countRun only accepts a strictly descending run (<, never <=): reversing a run with equal neighbours would swap them, and the whole point of a stable sort is that equal keys never trade places.
binaryInsertion binary-searches the slot (probe) but still shifts the tail one slot at a time: the search saves comparisons, the shift is the price of an array. Its insert snapshot is taken before that shift, unlike the insertion-sort lesson's post-write one.
mergeCollapse checks only the top three runs, exactly as the 2002 code did. That is the check the 2015 KeY proof found too weak: CPython and Java now also look at the fourth run, a case no array this small can ever reach.
merge copies only the left run into buf and writes back from the left, so the right run is never copied and never overwritten before it is read; ties go left (left <= a[j]), which is what keeps the merge stable. Missing versus CPython is galloping: the exponential search it switches to when one run keeps winning.

Tim Peters wrote Timsort in 2002 for Python's list.sort, building on Peter McIlroy's 1993 idea of a merge sort that exploits the runs already present in real data. It finds stretches that are already ascending or descending, pads short ones with binary insertion, and merges runs from a stack under invariants that keep the merges balanced. Java adopted it in 2011 and the JavaScript engines followed.

1993Peter McIlroy - Presents 'Optimistic Sorting and Information Theoretic Complexity' at SODA: a merge sort that adapts to the order already in its input, the seed of Timsort's run detection and galloping.source
2002Tim Peters - Writes Timsort for CPython 2.3's list.sort and documents every design decision in listsort.txt, still the primary reference.source
2011Joshua Bloch - Java 7 ships his port of Tim Peters's C code as Arrays.sort for objects, replacing the old modified merge sort.source
2015Stijn de Gouw and colleagues - Trying to prove the Java port correct with the KeY verifier, find that the run-stack invariant check is too weak and can crash on huge inputs; Python, Java, and Android are patched.source
2018V8 team - Chrome 70 switches Array.prototype.sort to Timsort, finally making JavaScript's sort stable in V8.source

Used today

Python's list.sort and sorted - Every Python sort since 2.3 has been Timsort; 3.11 kept its run finding but switched the merge policy to powersort.
Java and Android - Arrays.sort and Collections.sort on objects use the Java port, and Android's runtime inherited it.
V8 in Chrome and Node - Array.prototype.sort has been Timsort since V8 7.0 (Chrome 70), which is what made it stable.

n24

runs: 0
merges: 0
comparisons: 0
minrun: 6

timsort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** One entry on the run stack: a sorted stretch a[start..start+length). */interface Run {  readonly start: number;  readonly length: number;}/** * Timsort: find the runs the data already has (a strictly descending * run is reversed in place), extend short runs to minrun with binary * insertion sort, and merge runs off a stack whose two invariants keep * the merges balanced. Faithful to CPython's listsort minus galloping. * minMerge is 8 here instead of CPython's 64 so several runs stay * visible at the demo's sizes (n = 16..40). * * Time: O(n log n) worst case, O(n) when already sorted. Space: O(n) extra. */export class Timsort implements SortAlgorithm {  readonly name = "timsort";  /** Runs shorter than minrun (derived from this) get extended (CPython: 64). */  readonly minMerge = 8;  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    const n = a.length;    const n = array.length;    if (n < 2) return a;    if (n < 2) return array;    const minrun = this.minRun(n);    const runs: Run[] = [];    let lo = 0;    let low = 0;    while (lo < n) {    while (low < n) {      let hi = this.countRun(a, lo);      let high = this.countRun(array, low);      if (hi - lo < minrun) {      if (high - low < minrun) {        const end = Math.min(lo + minrun, n);        const end = Math.min(low + minrun, n);        this.binaryInsertion(a, lo, end, hi);        this.binaryInsertion(array, low, end, high);        hi = end;        high = end;      }      runs.push({ start: lo, length: hi - lo });      runs.push({ start: low, length: high - low });      this.mergeCollapse(a, runs);      this.mergeCollapse(array, runs);      lo = hi;      low = high;    }    while (runs.length > 1) this.mergeAt(a, runs, runs.length - 2);    while (runs.length > 1) this.mergeAt(array, runs, runs.length - 2);    return a;    return array;  }  /** CPython's rule: n's leading bits, plus one if any dropped bit was set. */  private minRun(n: number): number {    let r = 0;    while (n >= this.minMerge) {      r |= n & 1;      n >>= 1;    }    return n + r;  }  /** End of the natural run at lo; a strictly descending run is reversed. */  private countRun(a: number[], lo: number): number {  private countRun(array: number[], low: number): number {    let hi = lo + 1;    let high = low + 1;    if (hi === a.length) return hi;    if (high === array.length) return high;    const descending = a[hi]! < a[lo]!;    const descending = array[high]! < array[low]!;    while (hi < a.length && (descending ? a[hi]! < a[hi - 1]! : a[hi]! >= a[hi - 1]!)) {    while (high < array.length && (descending ? array[high]! < array[high - 1]! : array[high]! >= array[high - 1]!)) {      hi++;      high++;    }    // ▸ found a natural run: ascending, or descending (reverse it)    this.tracer?.emit("run", { descending, hi, lo, array: [...a] });    this.tracer?.emit("run", { descending, high, low, array: [...array] });    if (descending) this.reverse(a, lo, hi);    if (descending) this.reverse(array, low, high);    return hi;    return high;  }  private reverse(a: number[], lo: number, hi: number): void {  private reverse(array: number[], low: number, high: number): void {    for (let i = lo, j = hi - 1; i < j; i++, j--) {    for (let i = low, j = high - 1; i < j; i++, j--) {      const held = a[i]!;      const held = array[i]!;      a[i] = a[j]!;      array[i] = array[j]!;      a[j] = held;      array[j] = held;    }  }  /** Grow the sorted a[lo..start) to a[lo..end), binary-searching each key's slot. */  private binaryInsertion(a: number[], lo: number, end: number, start: number): void {  private binaryInsertion(array: number[], low: number, end: number, start: number): void {    for (let i = start; i < end; i++) {      const key = a[i]!;      const key = array[i]!;      let left = lo;      let left = low;      let right = i;      while (left < right) {        const probe = Math.floor((left + right) / 2);        // ▸ binary search the key's slot in the run so far        this.tracer?.emit("probe", { i, key, probe, array: [...a] });        this.tracer?.emit("probe", { i, key, probe, array: [...array] });        if (key < a[probe]!) right = probe;        if (key < array[probe]!) right = probe;        else left = probe + 1;      }      // Snapshot before the shift: a[i] still holds the key.      // ▸ shift the run right by one and drop the key in      this.tracer?.emit("insert", { at: left, i, key, array: [...a] });      this.tracer?.emit("insert", { at: left, i, key, array: [...array] });      for (let k = i; k > left; k--) a[k] = a[k - 1]!;      for (let k = i; k > left; k--) array[k] = array[k - 1]!;      a[left] = key;      array[left] = key;    }  }  /** Merge until the top three run lengths satisfy x > y + z and y > z. */  private mergeCollapse(a: number[], runs: Run[]): void {  private mergeCollapse(array: number[], runs: Run[]): void {    while (runs.length > 1) {      let n = runs.length - 2;      if (n > 0 && runs[n - 1]!.length <= runs[n]!.length + runs[n + 1]!.length) {        if (runs[n - 1]!.length < runs[n + 1]!.length) n--;        this.mergeAt(a, runs, n);        this.mergeAt(array, runs, n);      } else if (runs[n]!.length <= runs[n + 1]!.length) {        this.mergeAt(a, runs, n);        this.mergeAt(array, runs, n);      } else {        break;      }    }  }  /** Merge stack entries i and i + 1 (adjacent in the array) into one run. */  private mergeAt(a: number[], runs: Run[], i: number): void {  private mergeAt(array: number[], runs: Run[], i: number): void {    const lo = runs[i]!.start;    const low = runs[i]!.start;    const mid = runs[i + 1]!.start;    const hi = mid + runs[i + 1]!.length;    const high = mid + runs[i + 1]!.length;    const stack = runs.map((r) => r.length);    // ▸ a stack rule broke, or nothing is left: merge two runs    this.tracer?.emit("merge", { hi, lo, mid, stack, array: [...a] });    this.tracer?.emit("merge", { high, low, mid, stack, array: [...array] });    this.merge(a, lo, mid, hi);    this.merge(array, low, mid, high);    runs.splice(i, 2, { start: lo, length: hi - lo });    runs.splice(i, 2, { start: low, length: high - low });  }  /** Merge a[lo..mid) and a[mid..hi) through a copy of the left run. */  private merge(a: number[], lo: number, mid: number, hi: number): void {  private merge(array: number[], low: number, mid: number, high: number): void {    const buf = a.slice(lo, mid);    const leftCopy = array.slice(low, mid);    let i = lo;    let i = low;    let j = mid;    for (let k = lo; i < mid; k++) {    for (let k = low; i < mid; k++) {      const left = buf[i - lo]!;      const left = leftCopy[i - low]!;      // ▸ compare the buffered left front with the right front      if (j < hi) this.tracer?.emit("compare", { hi, i, j, left, lo, right: a[j]!, array: [...a] });      if (j < high) this.tracer?.emit("compare", { high, i, j, left, low, right: array[j]!, array: [...array] });      const fromLeft = j === hi || left <= a[j]!;      const fromLeft = j === high || left <= array[j]!;      // ▸ write the smaller one into place; ties go left      this.tracer?.emit("write", { from: fromLeft ? i : j, hi, lo, to: k, array: [...a] });      this.tracer?.emit("write", { from: fromLeft ? i : j, high, low, to: k, array: [...array] });      a[k] = fromLeft ? left : a[j]!;      array[k] = fromLeft ? left : array[j]!;      if (fromLeft) i++;      else j++;    }  }}

The array before sorting. Timsort first looks for runs the data already has.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** One entry on the run stack: a sorted stretch a[start..start+length). */interface Run { readonly start: number; readonly length: number;}/** * Timsort: find the runs the data already has (a strictly descending * run is reversed in place), extend short runs to minrun with binary * insertion sort, and merge runs off a stack whose two invariants keep * the merges balanced. Faithful to CPython's listsort minus galloping. * minMerge is 8 here instead of CPython's 64 so several runs stay * visible at the demo's sizes (n = 16..40). * * Time: O(n log n) worst case, O(n) when already sorted. Space: O(n) extra. */export class Timsort implements SortAlgorithm { readonly name = "timsort"; /** Runs shorter than minrun (derived from this) get extended (CPython: 64). */ readonly minMerge = 8; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; const n = a.length; const n = array.length; if (n < 2) return a; if (n < 2) return array; const minrun = this.minRun(n); const runs: Run[] = []; let lo = 0; let low = 0; while (lo < n) { while (low < n) { let hi = this.countRun(a, lo); let high = this.countRun(array, low); if (hi - lo < minrun) { if (high - low < minrun) { const end = Math.min(lo + minrun, n); const end = Math.min(low + minrun, n); this.binaryInsertion(a, lo, end, hi); this.binaryInsertion(array, low, end, high); hi = end; high = end; } runs.push({ start: lo, length: hi - lo }); runs.push({ start: low, length: high - low }); this.mergeCollapse(a, runs); this.mergeCollapse(array, runs); lo = hi; low = high; } while (runs.length > 1) this.mergeAt(a, runs, runs.length - 2); while (runs.length > 1) this.mergeAt(array, runs, runs.length - 2); return a; return array; } /** CPython's rule: n's leading bits, plus one if any dropped bit was set. */ private minRun(n: number): number { let r = 0; while (n >= this.minMerge) { r |= n & 1; n >>= 1; } return n + r; } /** End of the natural run at lo; a strictly descending run is reversed. */ private countRun(a: number[], lo: number): number { private countRun(array: number[], low: number): number { let hi = lo + 1; let high = low + 1; if (hi === a.length) return hi; if (high === array.length) return high; const descending = a[hi]! < a[lo]!; const descending = array[high]! < array[low]!; while (hi < a.length && (descending ? a[hi]! < a[hi - 1]! : a[hi]! >= a[hi - 1]!)) { while (high < array.length && (descending ? array[high]! < array[high - 1]! : array[high]! >= array[high - 1]!)) { hi++; high++; } // ▸ found a natural run: ascending, or descending (reverse it) this.tracer?.emit("run", { descending, hi, lo, array: [...a] }); this.tracer?.emit("run", { descending, high, low, array: [...array] }); if (descending) this.reverse(a, lo, hi); if (descending) this.reverse(array, low, high); return hi; return high; } private reverse(a: number[], lo: number, hi: number): void { private reverse(array: number[], low: number, high: number): void { for (let i = lo, j = hi - 1; i < j; i++, j--) { for (let i = low, j = high - 1; i < j; i++, j--) { const held = a[i]!; const held = array[i]!; a[i] = a[j]!; array[i] = array[j]!; a[j] = held; array[j] = held; } } /** Grow the sorted a[lo..start) to a[lo..end), binary-searching each key's slot. */ private binaryInsertion(a: number[], lo: number, end: number, start: number): void { private binaryInsertion(array: number[], low: number, end: number, start: number): void { for (let i = start; i < end; i++) { const key = a[i]!; const key = array[i]!; let left = lo; let left = low; let right = i; while (left < right) { const probe = Math.floor((left + right) / 2); // ▸ binary search the key's slot in the run so far this.tracer?.emit("probe", { i, key, probe, array: [...a] }); this.tracer?.emit("probe", { i, key, probe, array: [...array] }); if (key < a[probe]!) right = probe; if (key < array[probe]!) right = probe; else left = probe + 1; } // Snapshot before the shift: a[i] still holds the key. // ▸ shift the run right by one and drop the key in this.tracer?.emit("insert", { at: left, i, key, array: [...a] }); this.tracer?.emit("insert", { at: left, i, key, array: [...array] }); for (let k = i; k > left; k--) a[k] = a[k - 1]!; for (let k = i; k > left; k--) array[k] = array[k - 1]!; a[left] = key; array[left] = key; } } /** Merge until the top three run lengths satisfy x > y + z and y > z. */ private mergeCollapse(a: number[], runs: Run[]): void { private mergeCollapse(array: number[], runs: Run[]): void { while (runs.length > 1) { let n = runs.length - 2; if (n > 0 && runs[n - 1]!.length <= runs[n]!.length + runs[n + 1]!.length) { if (runs[n - 1]!.length < runs[n + 1]!.length) n--; this.mergeAt(a, runs, n); this.mergeAt(array, runs, n); } else if (runs[n]!.length <= runs[n + 1]!.length) { this.mergeAt(a, runs, n); this.mergeAt(array, runs, n); } else { break; } } } /** Merge stack entries i and i + 1 (adjacent in the array) into one run. */ private mergeAt(a: number[], runs: Run[], i: number): void { private mergeAt(array: number[], runs: Run[], i: number): void { const lo = runs[i]!.start; const low = runs[i]!.start; const mid = runs[i + 1]!.start; const hi = mid + runs[i + 1]!.length; const high = mid + runs[i + 1]!.length; const stack = runs.map((r) => r.length); // ▸ a stack rule broke, or nothing is left: merge two runs this.tracer?.emit("merge", { hi, lo, mid, stack, array: [...a] }); this.tracer?.emit("merge", { high, low, mid, stack, array: [...array] }); this.merge(a, lo, mid, hi); this.merge(array, low, mid, high); runs.splice(i, 2, { start: lo, length: hi - lo }); runs.splice(i, 2, { start: low, length: high - low }); } /** Merge a[lo..mid) and a[mid..hi) through a copy of the left run. */ private merge(a: number[], lo: number, mid: number, hi: number): void { private merge(array: number[], low: number, mid: number, high: number): void { const buf = a.slice(lo, mid); const leftCopy = array.slice(low, mid); let i = lo; let i = low; let j = mid; for (let k = lo; i < mid; k++) { for (let k = low; i < mid; k++) { const left = buf[i - lo]!; const left = leftCopy[i - low]!; // ▸ compare the buffered left front with the right front if (j < hi) this.tracer?.emit("compare", { hi, i, j, left, lo, right: a[j]!, array: [...a] }); if (j < high) this.tracer?.emit("compare", { high, i, j, left, low, right: array[j]!, array: [...array] }); const fromLeft = j === hi || left <= a[j]!; const fromLeft = j === high || left <= array[j]!; // ▸ write the smaller one into place; ties go left this.tracer?.emit("write", { from: fromLeft ? i : j, hi, lo, to: k, array: [...a] }); this.tracer?.emit("write", { from: fromLeft ? i : j, high, low, to: k, array: [...array] }); a[k] = fromLeft ? left : a[j]!; array[k] = fromLeft ? left : array[j]!; if (fromLeft) i++; else j++; } }}