jsschools

Merge Sort

Divide-and-conquer sort that recursively splits the array in half, sorts each half, and merges them back in order.

Spec ↗

Syntax

mergeSort(arr)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes The array to sort. Returns a new sorted array (out-of-place).

Returns

Array<number> — A new sorted array; the original is not mutated.

Examples

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), right.slice(j));
}

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

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
Output 
[ 3, 9, 10, 27, 38, 43, 82 ]

// Edge case: array of length 0 or 1
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const merge = (l, r) => {
    const out = []; let i = 0, j = 0;
    while (i < l.length && j < r.length)
      out.push(l[i] <= r[j] ? l[i++] : r[j++]);
    return out.concat(l.slice(i), r.slice(j));
  };
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}

console.log(mergeSort([]));
console.log(mergeSort([7]));
Output 
[]
[ 7 ]

Notes

| Case | Time | Space | |---------|------------|-------| | Best | O(n log n) | O(n) | | Average | O(n log n) | O(n) | | Worst | O(n log n) | O(n) | Merge sort is **stable** and has guaranteed O(n log n) performance regardless of input order. The O(n) auxiliary space is its main drawback for in-memory sorting. It is the preferred algorithm for linked lists (no random access needed) and for external sorting (data larger than RAM). JavaScript's `Array.prototype.sort` uses Timsort, which is a hybrid of merge sort and insertion sort.

See also