Will Chen

What is Merge Sort?

Merge Sort is an efficient sorting algorithm that has a time complexity of O(n log n) which is better than elementary sorting algorithms (such as bubble sort) which have a time complexity of O(n²).

Merge Sort works by splitting an array in half recursively until the sliced array you are working with is only one element. Once you have one element, then you want to merge it with another sub-array that is one element. Then, you have a merged sub-array that has two elements.

Click here for a visual explanation of how Merge Sort works

Approach

I implemented Merge Sort using a recursive approach and modularizing my code as much as possible.

Primary Code

var mergeSort = function( array ) {  
  // Split the array in half, recurse until the array has only 2 elements
  var arrs = splitArray( array );
  var firstHalf = arrs[0].length > 1 ? mergeSort( arrs[0] ) : arrs[0];
  var secondHalf = arrs[1].length > 1 ? mergeSort( arrs[1] ) : arrs[1];
  return mergeHalves(firstHalf, secondHalf);
};

I put the recursive logic in the main function and then relied on helper functions to implement the actual splitting and merging functionality.

One thing to note is that the variable arrs is a tuple. In this case, arrs is an array that has two elements that are arrays themselves.

Split Array - Helper Function

var splitArray = function(array){  
  var mid = Math.ceil(array.length/2);
  return [ array.slice(0, mid), array.slice(mid) ];
};

Merge Two Array Halves - Helper Function

var mergeHalves = function(firstHalf, secondHalf){  
  var output = [],
      firstIdx = 0,
      secondIdx = 0;
  // Iterate until both all of the elements in both halves are pushed into output
  while ( firstIdx < firstHalf.length || secondIdx < secondHalf.length ){
    if ( firstHalf[firstIdx] < secondHalf[secondIdx] || secondHalf[secondIdx] === undefined ){
      output.push(firstHalf[firstIdx]);
      firstIdx++;
    } else {
      output.push(secondHalf[secondIdx]);
      secondIdx++;
    }
  }
  return output;
};