var mergeSort = function (arr) {
  const len = arr.length;
  if (len === 1) return arr;
  const mid = Math.floor(len / 2);

  // 分
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // 治
  let res = [];
  while (left.length > 0 || right.length > 0) {
    // shift 推出
    if (left.length > 0 && right.length > 0) {
      res.push(left[0] < right[0] ? left.shift() : right.shift());
    } else if (left.length > 0) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }

  return res;
};