mergesort

index.js

function mergesort(xs) {
  if (xs.length < 2) {
    return xs
  }
  const n = xs.length / 2 | 0;
  return merge(mergesort(xs.slice(0, n)), mergesort(xs.slice(n)));
}

function merge(xs, ys) {
  const result = [];
  while (xs.length > 0 || ys.length > 0) {
    if (xs.length === 0) {
      return result.concat(ys);
    }
    if (ys.length === 0) {
      return result.concat(xs);
    }
    if(xs[0] < ys[0]) {
      result.push(xs.shift());
    } else {
      result.push(ys.shift());
    }
  }
  return result;
}