jsschools

Timsort

Hybrid stable sort (merge sort + insertion sort) that exploits existing runs of ordered data; used natively in JavaScript's Array.prototype.sort.

Spec ↗

Syntax

arr.sort((a, b) => a - b)  // JS built-in uses Timsort

Parameters

NameTypeRequiredDescription
compareFn (a: T, b: T) => number No Comparator returning negative if a < b, positive if a > b, 0 if equal. Without a comparator, elements are coerced to strings (common gotcha).

Returns

Array<T> — The same array, sorted in-place and returned.

Examples

// JavaScript's built-in sort IS Timsort in V8
const nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
nums.sort((a, b) => a - b);
console.log(nums);
Output 
[ 1, 1, 2, 3, 3, 4, 5, 5, 6, 9 ]

// Gotcha: without comparator, numbers are sorted as strings
const bad = [10, 9, 2, 21, 3];
bad.sort();
console.log(bad); // wrong!

const good = [10, 9, 2, 21, 3];
good.sort((a, b) => a - b);
console.log(good); // correct
Output 
[ 10, 2, 21, 3, 9 ]
[ 2, 3, 9, 10, 21 ]

Notes

| Case | Time | Space | |---------|------------|----------| | Best | O(n) | O(n) | | Average | O(n log n) | O(n) | | Worst | O(n log n) | O(n) | Timsort identifies natural ascending/descending **runs** and merges them. On already-sorted or nearly-sorted data it approaches O(n). It is **stable** — guaranteed by the ECMAScript spec since ES2019 (Array.prototype.sort must be stable). The minimum run size (minrun) is chosen between 32 and 64 so that insertion sort on each run is efficient. For most production JS code, just use `arr.sort()` with a comparator rather than implementing a sort yourself.

See also