Merge Sort
Divide in half, sort each half recursively, merge back.
How it works
Merge Sort is a divide-and-conquer algorithm that recursively splits the input in half, sorts each half, and then merges the two sorted halves into a single sorted sequence. This bottom-up iterative variant achieves the same result without recursion: it starts by treating every single element as a sorted subarray of length 1, then repeatedly merges adjacent pairs — doubling the subarray length each pass — until the entire array is sorted.
The merge step is the heart of the algorithm. Two sorted subarrays are combined by repeatedly comparing their leading elements and placing the smaller one into the output buffer. After the merge, the buffer is copied back. This approach guarantees O(n log n) comparisons in all cases — best, average, and worst — because the depth of the merge tree is always log₂ n, and each level does O(n) work.
Merge Sort is stable: equal elements drawn from the left subarray are always placed before equal elements from the right, preserving their original relative order. The trade-off is the O(n) auxiliary space required for the temporary merge buffer. This predictable performance and stability make it the foundation of Timsort, which is used by Python, Java, and Node.js for general-purpose sorting.
Complexity
Visualizer
Where it's used in the real world
Python / Java / Node.js — Timsort
General-purpose stable sort for all built-in sort functionsTimsort, the default sort in CPython, Java Arrays.sort (objects), and V8, is derived from merge sort. Its merge phase guarantees O(n log n) worst case and stability, making it safe for sorting complex objects by multiple keys without disturbing other fields.
External sorting of database files
Sorting datasets too large to fit in RAMExternal merge sort reads chunks of data from disk, sorts each chunk in memory, writes sorted runs back to disk, then repeatedly merges runs. Because merging only requires reading two streams sequentially, it minimises random-access I/O — critical when data lives on spinning disk or object storage.
GNU sort (coreutils)
Sorting large text files on the command lineGNU `sort` uses an external merge sort strategy: it splits input into chunks that fit in memory, sorts each with an in-memory algorithm, and then performs a k-way merge of the sorted temporary files. This allows it to sort files many times larger than available RAM with predictable performance.
Implementation
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left: number[], right: number[]): number[] {
const result: number[] = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i), right.slice(j));
}
// Usage
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]