Cairn
algorithms · sorting · O(n) best, O(n log n) worst

↩ back to Comparison Sorts

Timsort

Every other sort on this site picks one bet and keeps it: insertion sort bets the input is nearly sorted already, merge sort assumes nothing about it and guarantees O(n log n) regardless. Timsort, designed by Tim Peters for Python in 2002 and since adopted as the sort behind Java's Arrays.sort() for objects (and Android, and V8's stable-sort path), refuses to pick: it first looks for stretches of the array that are already sorted — real-world data is full of them, partially-sorted logs, nearly-sorted resubmissions, concatenated sorted chunks — and only falls back to insertion sort and merging where none exist. Find no order at all and it degrades to merge sort with extra bookkeeping. Find a mostly-sorted array and it can do a fraction of the work.

Try it

Enter a comma-separated list of numbers, then step through the sort. Real Timsort computes a minRun between 32 and 64 from the array length — too large to show more than one run on a short typed-in array, so this demo uses a small fixed minRun = 4 instead, labeled as such below; the algorithm itself is unmodified. Colored blocks are a natural run being detected or extended; the panel on the right is the run stack — pending runs waiting to merge, shown as length tags, newest on top.

Press Load, then Step through the sort.

Why it works

Finding a run. Scan forward from the current position: if the next element is >= the one before it, the run is ascending and keeps extending the same way; if it's smaller, the run is strictly descending and keeps extending only while each new element is strictly less than the last. A descending run gets reversed in place once it ends — safe specifically because it's strictly descending, no two equal elements sit inside it to have their order disturbed by the reversal. This is the same reasoning merge sort's own <= in its merge step protects for a different reason — see merge sort's own pitfalls on stability.

Extending short runs. A natural run shorter than minRun gets padded out to minRun elements (or the end of the array) using binary insertion sort — the same technique as insertion sort, except each new element's insertion point is found with a binary search instead of a linear backward scan. This doesn't change the O(n²) worst case for the insertion phase overall, since shifting elements into place is still linear — but it does cut the number of comparisons needed to find where each one goes, from linear to logarithmic.

Merging without losing the guarantee. Runs get pushed onto a stack as they're found. After every push, Timsort checks two rules on the top few run lengths and merges adjacent runs whenever a rule is violated: the third-from-top run must be longer than the combined length of the two above it, and the second-from-top must be longer than the top. Both rules exist to keep run lengths roughly exponential going down the stack — the same balance a self-balancing tree maintains on subtree heights — which is what turns "however the natural runs happened to fall" into a guaranteed O(n log n) total merge cost, the same bound plain merge sort gets by force-splitting exactly in half every time.

Reference implementation

Natural-run detection, binary-insertion extension, and the stack-based merge policy above, un-instrumented. This omits one real optimization production Timsort has and this page doesn't implement — see Pitfalls.

function minRunLength(n) {
  let r = 0;
  while (n >= 64) { r |= (n & 1); n >>= 1; }
  return n + r; // returns a value in [32, 64)
}

function countRunAndMakeAscending(arr, left, right) {
  let runEnd = left + 1;
  if (runEnd > right) return 1;
  if (arr[runEnd] < arr[left]) {
    while (runEnd <= right && arr[runEnd] < arr[runEnd - 1]) runEnd++;
    for (let lo = left, hi = runEnd - 1; lo < hi; lo++, hi--) {
      [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
    }
  } else {
    while (runEnd <= right && arr[runEnd] >= arr[runEnd - 1]) runEnd++;
  }
  return runEnd - left;
}

function binaryInsertionSort(arr, left, right, sortedUpTo) {
  for (let i = sortedUpTo; i <= right; i++) {
    const key = arr[i];
    let lo = left, hi = i;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (arr[mid] <= key) lo = mid + 1; else hi = mid;
    }
    for (let j = i; j > lo; j--) arr[j] = arr[j - 1];
    arr[lo] = key;
  }
}

function merge(arr, left, mid, right) {
  const leftArr = arr.slice(left, mid), rightArr = arr.slice(mid, right);
  let i = 0, j = 0, k = left;
  while (i < leftArr.length && j < rightArr.length) {
    arr[k++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
  }
  while (i < leftArr.length) arr[k++] = leftArr[i++];
  while (j < rightArr.length) arr[k++] = rightArr[j++];
}

function timSort(arr) {
  const n = arr.length;
  if (n < 2) return arr;
  const minRun = minRunLength(n);
  const runStarts = [], runLens = [];

  function mergeAt(i) {
    const s1 = runStarts[i], l1 = runLens[i], s2 = runStarts[i + 1], l2 = runLens[i + 1];
    merge(arr, s1, s2, s2 + l2);
    runLens[i] = l1 + l2;
    runStarts.splice(i + 1, 1);
    runLens.splice(i + 1, 1);
  }

  function collapse() {
    while (runStarts.length > 1) {
      const top = runStarts.length - 1;
      if (top >= 2 && runLens[top - 2] <= runLens[top - 1] + runLens[top]) {
        mergeAt(runLens[top - 2] < runLens[top] ? top - 2 : top - 1);
      } else if (runLens[top - 1] <= runLens[top]) {
        mergeAt(top - 1);
      } else break;
    }
  }

  let start = 0;
  while (start < n) {
    let runLen = countRunAndMakeAscending(arr, start, n - 1);
    const end = Math.min(start + minRun, n);
    if (runLen < end - start) {
      binaryInsertionSort(arr, start, end - 1, start + runLen);
      runLen = end - start;
    }
    runStarts.push(start);
    runLens.push(runLen);
    collapse();
    start += runLen;
  }
  while (runStarts.length > 1) mergeAt(runStarts.length - 2);
  return arr;
}

Adaptivity, measured

The claim "it exploits existing order" is easy to state and easy to get wrong in the details, so here it's counted rather than asserted. Both the real timSort above and the plain mergeSort from merge sort's own page ran, unmodified, on the same 1,000-element arrays below, with every <=/< comparison counted:

Run the same comparison yourself below, on data shaped either way, or on plain random data where neither algorithm has an edge:

Press "Count comparisons" to run both algorithms on the same 1,000-element array.

Pitfalls

No galloping mode here. Production Timsort adds one more trick this reference implementation leaves out: during a merge, if one side keeps winning several comparisons in a row, it switches to a binary search ("galloping") to pull a whole chunk from that side at once instead of comparing element by element. That's a real further speedup on top of what's measured above, not implemented here to keep the reference implementation reasonably short — the run-detection and stack-merge behavior above is genuine, not a simplification of it.

Small arrays never merge at all. minRunLength returns n itself whenever n < 64 — the whole array becomes a single run, extended (if needed) by binary insertion sort, with no merge step ever triggered. Real Timsort on a short array is binary insertion sort. The demo above only shows multiple runs merging because it substitutes a small fixed minRun for the real formula — worth knowing before assuming a small live example proves the merge logic runs in practice on small inputs, since it doesn't, not with the real threshold.

No advantage on genuinely random data — confirmed above (8,659 vs. 8,667 comparisons at n = 1,000 across repeated random trials, statistically tied) — and a real, if small, disadvantage on scattered disorder, also confirmed above. Timsort's worst case is still O(n log n), same as merge sort, but its bookkeeping (run detection, stack invariant checks) is pure overhead when there's no order to find.

A known subtlety in the merge invariant is not addressed here. The two-rule stack policy above is the original 2002 design; a 2015 paper by Peters and de Gouw found that certain long inputs could violate the intended stack-depth bound under those exact two rules and proposed a third rule to close the gap. Real production Timsort implementations adopted the fix; this page's reference implementation uses the original two rules, which is correct for every input this page tests but isn't the newest production algorithm word-for-word.

Complexity

Time: O(n) best case (the whole array is already one run, or close to it), O(n log n) worst case — the stack-merge policy above guarantees this the same way merge sort's forced halving does, regardless of how the natural runs happen to fall. Space: O(n) for the merge buffers, same as plain merge sort, plus O(log n) for the run stack itself. Stable: yes — ties inside an ascending run keep their original order, a strictly-descending run has no ties to disturb when reversed, and the merge step's <= favors the left (earlier) run on equal keys, exactly merge sort's own reasoning.

That combination — adaptive to real-world order, stable, with merge sort's worst-case guarantee as a floor — is why Timsort backs Python's sorted()/list.sort() and Java's Arrays.sort() for object arrays, rather than plain merge sort or insertion sort alone — it's built directly from both, using each one exactly where the other is weak.

See Choosing a Comparison Sort for how Timsort fits alongside the other ten comparison sorts on this site.