How do you implement merge sort in JavaScript?
Recursively split the array into two halves until single elements remain, then merge the sorted halves by repeatedly taking the smaller front element. It runs in O(n log n) time with O(n) extra space.
Explain it simply
An array with one element is already sorted. That is the base case. To sort a bigger array, sort the left half, sort the right half, then merge them.
Merging two sorted piles is easy: compare the top card of each pile, take the smaller, and repeat. Using <= when comparing keeps equal items in their original order, which makes the sort stable.
Example
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));
const result = [];
let i = 0;
let 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));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10])); // Output: [3,9,10,27,38,43,82]Complexity
Time O(n log n) always, space O(n).
What to say in the interview
"Base case: an array of length one is sorted. Otherwise I split it, sort both halves recursively and merge them with two pointers. The depth is log n and each level does O(n) work, so it is O(n log n) in every case, with O(n) extra space."
Common mistakes
- Using < instead of <= in the merge, which makes the sort unstable.
- Forgetting to append the leftover elements after one half runs out.