2020-01-28 归并排序

function merge(left, right) {
  const len_left = left && left.length
  const len_right = right && right.length
  let res = []
  let index_left = 0
  let index_right = 0

  while (index_left < len_left && index_right < len_right) {
    res.push((left[index_left] < right[index_right]) ? left[index_left++] : right[index_right++])
  }

  while (index_left < len_left) {
    res.push(left[index_left++])
  }

  while (index_right < len_right) {
    res.push(right[index_right++])
  }

  return res
}

function mergeSort(arr) {
  const len = arr.length
  if (len <= 1) return arr

  const mid = ~~(len / 2)
  const left = arr.slice(0, mid)
  const right = arr.slice(mid)

  return merge(mergeSort(left), mergeSort(right))
}