Tim Sort
The pragmatist's sort: detect the runs real data already has, insertion-sort the small stuff, merge the rest — the algorithm behind Python, Java, and V8.
Hands on Interactive visualization
Implementation Code
// Simplified TimSort: fixed RUN, insertion-sorted runs, doubling merges.
// (Production TimSort adds run detection, min-run sizing, galloping.)
const RUN = 16;
function insertionSortRange(a: number[], lo: number, hi: number): void {
for (let i = lo + 1; i <= hi; i++) {
const key = a[i];
let j = i - 1;
while (j >= lo && a[j] > key) {
a[j + 1] = a[j]; // shift right
j--;
}
a[j + 1] = key;
}
}
function merge(a: number[], lo: number, mid: number, hi: number): void {
const left = a.slice(lo, mid + 1);
const right = a.slice(mid + 1, hi + 1);
let i = 0, j = 0, k = lo;
while (i < left.length && j < right.length) {
// <= keeps equal elements in original order (stability)
a[k++] = left[i] <= right[j] ? left[i++] : right[j++];
}
while (i < left.length) a[k++] = left[i++];
while (j < right.length) a[k++] = right[j++];
}
export function timSort(a: number[]): number[] {
const n = a.length;
for (let lo = 0; lo < n; lo += RUN) {
insertionSortRange(a, lo, Math.min(lo + RUN - 1, n - 1));
}
for (let width = RUN; width < n; width *= 2) {
for (let lo = 0; lo < n; lo += 2 * width) {
const mid = lo + width - 1;
const hi = Math.min(lo + 2 * width - 1, n - 1);
if (mid < hi) merge(a, lo, mid, hi);
}
}
return a;
}Big-O Complexity
Best case O(n) when the input is already one run (sorted or reverse-sorted). The merge buffer can be bounded to n/2 in full implementations.
In production When to use
TimSort is the default stable sort in Python (list.sort, sorted — with a powersort merge policy since 3.11), Java (Arrays.sort for objects, Collections.sort), and Android. If you call a stdlib sort on objects, you are probably running it.
V8 has implemented Array.prototype.sort with TimSort since 2018, so every array sort in Chrome and Node.js benefits from run detection on partially ordered data.
Real-world data is rarely random: log files mostly ordered by time, lists re-sorted after a few edits. TimSort's run detection turns that latent order into near-linear time.
Stability makes chained sorts correct: sort by secondary key, then by primary — ties preserve the earlier order. This is why object sorts in stdlibs must be stable, and why they chose TimSort.
Run-detection plus merging is the same shape as external sorting; systems that sort mostly-ordered streams (time-series ingestion, LSM compaction inputs) exploit existing runs the same way.
Trade-offs Strengths & weaknesses
- Adaptive: already-ordered regions are detected as runs and skipped past in O(n).
- Stable — safe for sorting records by multiple keys in sequence.
- Guaranteed O(n log n) worst case, unlike quicksort.
- Excellent on real-world data, which is almost never uniformly random.
- Battle-tested: decades of production use across Python, Java, and V8.
- Descending runs are reversed in O(n) and reused rather than destroyed.
- Significantly more complex to implement correctly than any classic sort.
- O(n) auxiliary memory for merges — not for tight embedded budgets.
- Higher constant overhead than insertion sort on tiny arrays (which is why it delegates to insertion sort below the min-run size).
- The original merge-invariant logic had a subtle bug found by formal verification in 2015 — a warning about its intricacy.
- Loses to radix/counting sorts on fixed-width integer keys.
Intuition Mental model
Tidying a bookshelf that is already half-organized
You never sort a real shelf from scratch — stretches of it are already in order. You spot those ordered stretches, fix up the tiny messy gaps by hand, then merge neighboring ordered stretches into longer ones.
- Walk the shelf and mark every stretch that is already in order (runs).
- A stretch running backwards? Flip the whole block at once — it's ordered now.
- Stretches that are too short get hand-sorted quickly (insertion sort).
- Merge neighboring stretches pairwise, keeping ties in their original order.
- Keep merges balanced — don't merge a shelf-length stretch with a three-book one unless you must.
Prep Interview questions
Why do standard libraries use TimSort for objects but quicksort variants for primitives?
What is a 'run' and what does min-run do?
How does TimSort achieve O(n) on sorted input?
What role does galloping play?
Why is TimSort's worst case still O(n log n)?
Watch out Common bugs
The classic TimSort bug: checking the invariant only for the top runs of the stack. Formal verification in 2015 showed the original could overflow its run stack; the fix checks deeper entries too.
Descending runs must be *strictly* descending before reversal. Reversing a run containing equal elements swaps their order and silently breaks stability.
Min-run should be 32–64 computed so n/minrun is close to a power of two; hardcoding it produces unbalanced final merges and measurable slowdowns.
Only adjacent runs may merge, and only in ways that preserve order between equal elements — merging out of order is both incorrect and unstable.
One screen Cheat sheet
Insertion sort for small runs + merge sort for the rest, exploiting order that already exists.
- Detects natural ascending/descending runs; reverses descending ones.
- Extends short runs to min-run (16–64) with insertion sort.
- Merges adjacent runs under stack invariants that bound depth to O(log n).
- Galloping mode block-copies when one run dominates a merge.
- Stable and adaptive — the default for Python, Java objects, and V8.