merge_sort.js

// merge sort
// https://en.wikipedia.org/wiki/Merge_sort

var sort = function(list) {
  // if list contains one element, it is sorted
  if (list.length <= 1) return list;

  // divide list in half into 2 sublists
  var middle = Math.floor(list.length / 2);
  var left = list.slice(0, middle);
  var right = list.slice(middle);

  // sort the sublists
  left = sort(left);
  right = sort(right);

  // merge the sublists
  return merge(left, right);
};

var merge = function(a, b) {
  var result = [];

  while (a.length || b.length) {
    if (a.length && b.length) {
      if (a[0] <= b[0]) {
        result.push(a.shift());
      } else {
        result.push(b.shift());
      }
    } else if (a.length) {
      result.push(a.shift());
    } else if (b.length) {
      result.push(b.shift());
    }
  }

  return result;
};