Merge Sort

Merge sort is the textbook divide-and-conquer sort. Split the list in half, sort each half (by splitting *it* in half, recursively), then merge the two sorted halves into one. A single-element list is already sorted, so the recursion bottoms out cleanly. Its great virtue: it runs in O(n log n) on every input, best or worst.

Merging two sorted lists is the easy part

The clever step is the merge, and it's almost trivial: with two already-sorted halves, the smallest remaining value is always at the front of one of them. Keep a pointer into each half, compare the two fronts, take the smaller, and advance that pointer. Repeat until both are drained.

1. 1Divide: split the array into a left and right half.
2. 2Recurse: sort each half with the same procedure, down to single elements.
3. 3Merge: walk both sorted halves, repeatedly copying the smaller front value into an auxiliary buffer.
4. 4Copy the merged buffer back — the whole range is now sorted.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]); // <= keeps it stable
    else out.push(right[j++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}