Algorithms | Merge Sort | JavaScript

merge-sort.js

// Merge Sort Algorithm implemented in JavaScript
// By @hackerrdave

function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  
  let midpoint = Math.floor(arr.length / 2);
  let leftHalf = arr.slice(0, midpoint); //slice an array of left-half items
  let rightHalf = arr.slice(midpoint); //slice an array of right-half items
  
  //recurse into each half until arrays are 1 item each
  //then merge() the sorted arrays on each layer of the stack
  return merge(mergeSort(leftHalf), mergeSort(rightHalf));
}

//first time this merge() gets called, the arr's are both 1 element long
//on each layer of the stack the arrs will be doubled and always be sorted
function merge(arrA, arrB) {
  let a = 0;
  let b = 0;
  let result = [];
  
  while (a < arrA.length && b < arrB.length) {
    if (arrA[a] < arrB[b]) {
      result.push(arrA[a]);
      a++;
    } else {
      result.push(arrB[b]);
      b++;
    }
  }

  //using slice to concat remaining items left in either arrA or arrB
  return result.concat(arrA.slice(a)).concat(arrB.slice(b)); 
}

//usage:
mergeSort([4,2,8,3,6,9,1]); //=> [1,2,3,4,6,8,9]