Merge Sort

mergeSort.js

function merge(a, b) {
  var result = [];
  var i = 0;
  var j = 0;
  
  while(i + j < a.length + b.length) {
    if (j >= b.length || a[i] <= b[j]) {
      result.push(a[i]);
      i++;
    } else {
      result.push(b[j]);
      j++;
    }
  }
  
  return result;
}

function sort(input) {
  if (input.length < 2) {
    return input;
  }
  
  var half = Math.floor(input.length / 2);
  
  return merge(
    sort(input.slice(0, half)),
    sort(input.slice(half))
  );
}

// [0, 1, 2, 2, 4, 4, 4, 5, 5, 7, 8, 8, 78]
console.log(sort([4, 5, 2, 78, 8, 0, 2, 5, 7, 1, 4, 8, 4]));