DEV Community

Andrew Lee
Andrew Lee

Posted on

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]
Enter fullscreen mode Exit fullscreen mode

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]

[]
Enter fullscreen mode Exit fullscreen mode
// 3 is smaller than 5
[8, 9]
[5, 50, 100]

[3]
Enter fullscreen mode Exit fullscreen mode
// 5 is smaller than 8
[8, 9]
[50, 100]

[3, 5]
Enter fullscreen mode Exit fullscreen mode
// 8 is smaller than 50
[9]
[50, 100]

[3, 5, 8]
Enter fullscreen mode Exit fullscreen mode
// 9 is smaller than 50
[]
[50, 100]

[3, 5, 8, 9]
Enter fullscreen mode Exit fullscreen mode
// There's no more left in one of the arrays
[]
[50, 100]

[3, 5, 8, 9]
Enter fullscreen mode Exit fullscreen mode
// Just push the rest in
[]
[]

[3, 5, 8, 9, 50, 100]
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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

     [50, 8, 3, 5, 100, 9]
[3, 8, 50]          [5, 9, 100]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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));
}
Enter fullscreen mode Exit fullscreen mode

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]));
Enter fullscreen mode Exit fullscreen mode

Top comments (0)