Tim Sort
Hybrid of merge sort and insertion sort. Used in Python, Java, and V8.
How it works
Timsort is a hybrid sorting algorithm developed by Tim Peters in 2002 for CPython. It combines the strengths of insertion sort (excellent for small or nearly-sorted arrays) with merge sort (reliable O(n log n) for large inputs) and exploits the natural order already present in real-world data.
The algorithm works in two phases. In Phase 1, the input is divided into fixed-length chunks called *runs* (size `minRun`, typically 32–64 in production). Each run is sorted in place using insertion sort, which is cache-friendly and fast on small arrays. If a natural ascending or descending run longer than `minRun` is found, it is used directly (descending runs are reversed); this is the *adaptive* property that gives Timsort O(n) best-case performance on already-sorted data.
In Phase 2, sorted runs are merged using a bottom-up approach similar to merge sort. Timsort maintains a stack of runs and applies merge rules (the *galloping* optimisation and *run length invariants*) to ensure runs of similar size are merged first, keeping the merge tree balanced and the total work at O(n log n). The merge step is stable — equal elements from the left run always precede those from the right — which is why Timsort is the default sort in Python, Java (objects), and JavaScript (V8).
Complexity
Visualizer
Where it's used in the real world
CPython — built-in sorted() and list.sort()
General-purpose stable sort for all Python listsTim Peters designed Timsort specifically for CPython after observing that real-world data often contains partially sorted sequences. Its adaptive behaviour makes it significantly faster than pure merge sort on such inputs, while its O(n log n) guarantee keeps it safe for adversarial data.
Java — Arrays.sort(Object[]) and Collections.sort()
Sorting object arrays and collectionsJava 7 replaced the older merge sort in Arrays.sort for objects with Timsort. The stability guarantee is critical: sorting a table by column B and then by column A must preserve the B-order for ties in A — only a stable algorithm guarantees this without extra bookkeeping.
V8 JavaScript engine — Array.prototype.sort()
Default array sorting in Node.js and ChromeV8 switched from quicksort to Timsort in 2019 (Node.js ≥ 12 / Chrome 70) to comply with the ECMAScript spec requirement for a stable sort. The real-world speed advantage on partially ordered data (e.g. DOM node lists, already-sorted API responses) made it the natural choice.
Implementation
const MIN_RUN = 32;
// Insertion sort in place on arr[left..right]
function insertionSort(arr: number[], left: number, right: number): void {
for (let i = left + 1; i <= right; i++) {
const key = arr[i];
let j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Merge arr[left..mid] with arr[mid+1..right] in place (using temp buffer)
function merge(arr: number[], left: number, mid: number, right: number): void {
const leftPart = arr.slice(left, mid + 1);
const rightPart = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < leftPart.length && j < rightPart.length) {
arr[k++] = leftPart[i] <= rightPart[j] ? leftPart[i++] : rightPart[j++];
}
while (i < leftPart.length) arr[k++] = leftPart[i++];
while (j < rightPart.length) arr[k++] = rightPart[j++];
}
export function timSort(arr: number[]): number[] {
const a = [...arr];
const n = a.length;
// Phase 1: sort each run with insertion sort
for (let i = 0; i < n; i += MIN_RUN) {
insertionSort(a, i, Math.min(i + MIN_RUN - 1, n - 1));
}
// Phase 2: merge runs bottom-up
for (let width = MIN_RUN; width < n; width *= 2) {
for (let left = 0; left < n; left += 2 * width) {
const mid = Math.min(left + width - 1, n - 1);
const right = Math.min(left + 2 * width - 1, n - 1);
if (mid < right) merge(a, left, mid, right);
}
}
return a;
}
// Usage
console.log(timSort([15, 3, 29, 7, 12, 3, 38, 18, 6, 22, 11, 45]));
// [3, 3, 6, 7, 11, 12, 15, 18, 22, 29, 38, 45]