TimSort

TimSort was designed by Tim Peters in 2002 for CPython and is now the sorting algorithm used by Python, Java (for objects), and V8 (Node.js and Chrome’s JavaScript engine, since V8 version 7.0 released in 2018). It is a hybrid of merge sort and insertion sort, engineered to exploit the ordered subsequences that almost always appear in real-world data.

Core Ideas

Natural Runs

A run is a maximal already-sorted (or strictly descending) subsequence of the input. TimSort scans the array once and identifies these runs. Descending runs are reversed in-place so all runs are ascending. If a run is shorter than a threshold called minRun (typically 32–64), insertion sort extends it to that length, taking advantage of insertion sort’s O(n) best case on nearly-sorted data.

Merge with a Run Stack

Identified runs are pushed onto a stack. TimSort maintains two invariants about the run lengths on the stack (named X, Y, Z from top to bottom):

• Z > Y + X
• Y > X

When either invariant is violated the two smallest adjacent runs are merged. This strategy balances run sizes and keeps the stack depth at O(log n), which bounds the total merge cost at O(n log n) in the worst case.

Galloping Mode

During a merge, if one side consistently wins many comparisons in a row (the default threshold is 7), TimSort switches to a binary-search-based galloping mode that finds the boundary of the winning run in O(log k) comparisons instead of k comparisons. On nearly-sorted data where large contiguous regions from one half dominate, galloping delivers a significant speed-up.

The Critical JS Gotcha: Always Pass a Comparator

Array.prototype.sort without a comparator converts every element to a string before comparing. This is correct for strings but produces wrong results for numbers:

// Wrong — default string comparison
const nums = [10, 9, 2, 1, 100];
nums.sort();
console.log(nums);
// => [1, 10, 100, 2, 9]  -- lexicographic order!

// Correct — numeric comparator
nums.sort((a, b) => a - b);
console.log(nums);
// => [1, 2, 9, 10, 100]

// Descending
nums.sort((a, b) => b - a);
console.log(nums);
// => [100, 10, 9, 2, 1]

This is one of the most common bugs in JavaScript code that deals with numeric data.

Stability Guarantee

Since V8 7.0 (Node.js 11 / Chrome 70), Array.prototype.sort is guaranteed stable. The ECMAScript 2019 specification formally requires stability. Older engines (V8 < 7.0) used an unstable quicksort for arrays with more than 10 elements — another reason to upgrade or use a polyfill if targeting legacy environments.

// Stability in practice: sort by last name, then by first name
const people = [
  { first: "Alice", last: "Smith" },
  { first: "Bob",   last: "Jones" },
  { first: "Carol", last: "Smith" },
];

// Sort by last name — Alice Smith and Carol Smith must stay in original order
people.sort((a, b) => a.last.localeCompare(b.last));
console.log(people.map((p) => p.first));
// => ["Bob", "Alice", "Carol"]  -- Alice before Carol: stable!

Complexity

The O(n) best case occurs when the input is already sorted — each element forms its own run that passes the invariant checks without triggering any merges.

When to Think About TimSort as a Developer

You rarely implement TimSort yourself. The takeaway for day-to-day JavaScript is:

1. Always provide a comparator when sorting numbers, dates, or custom objects.
2. Rely on Array.prototype.sort for stable ordering in any modern JS environment.
3. Understand that for nearly-sorted data, the built-in sort is close to O(n) — you do not need to special-case it.

Up Next

With sorting covered, the next section moves to search algorithms — starting with the simplest approach that works on any unsorted collection.