2. 排序

归并排序（Divide && Conquer）

function mergeSort(arr) {
  const len = arr.length
  if (len < 2) return arr
  // 取中位索引，分割左数组和右数组
  let middle = Math.floor(len / 2),
      left = arr.slice(0, middle),
      right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
  const ans = []
  while(left.length && right.length) {
    if (left[0] <= right[0]) {
      ans.push(left.shift())
    } else {
      ans.push(right.shift())
    }
  }
  while(left.length) ans.push(left.shift())
  while(right.length) ans.push(right.shift())
  return ans
}

快速排序

function quickSort(arr) {
  if (arr.length <=1) return arr
  const pivot = Math.floor(arr.length / 2)
  const left = [],
        right = []
}

堆排序