Bottoms Up Introduction to Merge Sort with JavaScript

Merge

Let's say we have two sorted arrays...how would we merge the two?

[3, 8, 9]
[5, 50, 100]

We can find the lowest number from both arrays and put it into a new merged array. Since the arrays are sorted, the lowest number of each array will be at the front. This means we just have to compare the first element in each sorted array to determine what the smallest number is.

[3, 8, 9]
[5, 50, 100]

[]

// 3 is smaller than 5
[8, 9]
[5, 50, 100]

[3]

// 5 is smaller than 8
[8, 9]
[50, 100]

[3, 5]

// 8 is smaller than 50
[9]
[50, 100]

[3, 5, 8]

// 9 is smaller than 50
[]
[50, 100]

[3, 5, 8, 9]

// There's no more left in one of the arrays
[]
[50, 100]

[3, 5, 8, 9]

// Just push the rest in
[]
[]

[3, 5, 8, 9, 50, 100]

Implementation

function merge(left, right) {
  const output = [];

  while(left.length && right.length) {
    if(left[0] <= right[0]) {
      output.push(left.shift());
    } else {
      output.push(right.shift());
    }
  }

  while(left.length) {
    output.push(left.shift());
  }

  while(right.length) {
    output.push(right.shift());
  }

  return output;
}

Merge Sort

We know how to merge two sorted arrays, what does that have to do with merge sort? What do we do when we are given an array that is not sorted? How do we split it up into two sorted arrays?

We keep splitting the array in half until we come to a situation where there is only one element left in an array. When there's only one element in the array, we can ensure that it is sorted. If we have two arrays with one element each, it means that we can merge the two!

     [50, 8, 3, 5, 100, 9]
[50, 8, 3]          [5, 100, 9]
[50, 8] [3]         [5, 100] [9]
[50] [8]            [5] [100]

We can now merge [50] with [8] which turns into [8, 50]

     [50, 8, 3, 5, 100, 9]
[50, 8, 3]          [5, 100, 9]
[8, 50] [3]         [5, 100] [9]
                    [5] [100]

Similarly we can merge [5] with [100] which turns into [5, 100]

     [50, 8, 3, 5, 100, 9]
[50, 8, 3]          [5, 100, 9]
[8, 50] [3]         [5, 100] [9]

Now lets merge [8, 50] with [3] which turns into [3, 8, 50]

     [50, 8, 3, 5, 100, 9]
[3, 8, 50]          [5, 100, 9]
                    [5, 100] [9]

And merge [5, 100] with [9] which turns into [5, 9, 100]

     [50, 8, 3, 5, 100, 9]
[3, 8, 50]          [5, 9, 100]

We are now left with two sorted arrays [3, 8, 50] and [5, 9, 100] which we can merge into [3, 5, 8, 9, 50, 100].

     [3, 5, 8, 9, 50, 100]

Implementation

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

Full Implementation

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

function merge(left, right) {
  const output = [];

  while(left.length && right.length) {
    if(left[0] <= right[0]) {
      output.push(left.shift());
    } else {
      output.push(right.shift());
    }
  }

  while(left.length) {
    output.push(left.shift());
  }

  while(right.length) {
    output.push(right.shift());
  }

  return output;
}

console.log(mergeSort([50, 8, 3, 5, 100, 9]));