How does merge sort work?

Merge sort is the clearest divide-and-conquer algorithm. The divide step is trivial: split at the midpoint. The combine step does the real work: merge two sorted arrays by repeatedly taking the smaller front element.

function mergeSort(values) {
  if (values.length <= 1) return values;
  const mid = Math.floor(values.length / 2);
  const left = mergeSort(values.slice(0, mid));
  const right = mergeSort(values.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  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++]);
  }
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}

Why the complexity is O(n log n)

• There are log n levels of splitting
• Each level merges a total of n elements
• The merge work is linear per level
• The recursion tree has log n height, so stack usage is O(log n)

The main cost is the auxiliary array used during merging. A linked list can be merged without allocating a new list, which is one reason merge sort is attractive for linked lists. It is also a natural fit for external sorting where data does not fit in memory.