Merge sort (recursion)

Medium TimeO(n log n) SpaceO(n)

Given an array arr of numbers, return a new array holding the same values in ascending order, sorted by splitting the array in half and merging the sorted halves back together. The input is left exactly as it was, and an array of 0 or 1 values is already sorted.

Examples

Example 1

Input
arr = [5, 2, 8, 1, 9, 3]
Output
[1,2,3,5,8,9]
The same six values, ascending: 1, 2, 3, 5, 8, 9.

Example 2

Input
arr = [4, 1, 4]
Output
[1,4,4]
Both 4s come back — sorting rearranges, it does not remove.

The Code

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(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) out.push(a[i++]);
    else out.push(b[j++]);
  }
  return out.concat(a.slice(i)).concat(b.slice(j));
}
mergeSort([5, 2, 8, 1, 9, 3]);
Done

The first 21 calls, of 31. This one does not fit on a page.

Step through mergeSort([5, 2, 8, 1, 9, 3]) call by call

More like this

All sorting examples (8) →