Merge Sort
Sort by recursively splitting in half, sorting each side, and merging back ā guaranteed O(n log n) regardless of input, stable.
Intent & Description
šÆ Intent
Sort with guaranteed O(n log n) performance on any input ā no pivot trap, no worst case ā while preserving the relative order of equal elements.
š Context
You need predictable performance on adversarial or unknown input, or you need a stable sort (equal elements must preserve their original relative order). Quick sort’s O(nĀ²) worst case on sorted or nearly-sorted input is unacceptable. Merge sort has no such trap.
š” Solution
Recursively split the array in half until each sub-array is a single element (trivially sorted). Merge adjacent sorted sub-arrays by repeatedly picking the smaller front element from either side ā until the full sorted array is reconstructed. Every level of the recursion does O(n) merge work across O(log n) levels.
Real-world Use Case
š TL;DR
Guaranteed O(n log n), stable, no worst-case trap. Costs O(n) extra memory ā the price of predictability over quick sort’s in-place gamble.
Advantages
- Guaranteed O(n log n) ā no input shape triggers a worse case
- Stable ā equal elements preserve their original relative order
- Excellent for linked lists and external (disk-based) sorting
Disadvantages
- O(n) extra space ā requires an auxiliary array the size of the input
- Slower than quick sort in practice on arrays ā extra allocation and copy overhead adds up
- More implementation complexity than quick sort
function mergeSort(arr) {
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, right) {
const result = [];
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)).concat(right.slice(j));
}
// Usage
const unsorted = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(unsorted)); // [11, 12, 22, 25, 34, 64, 90]