归并排序

归并排序的核心思想是分治，将一个问题分解成多个子问题

归并排序是通过将数组分解成足够小的数组(只包含一个元素)，然后通过合并两个有序数组（单个元素的数组可认为是有序数组）解决问题。其重点在于数组的分解
Array.prototype.sort方法没有规定使用哪种排序算法，允许浏览器自定义，FireFox使用的是归并排序法，而Chrome使用的是快速排序法(大于22个数)
时间复杂度O(nlog(n)) 空间复杂度O(n)

function mergeSort(arr) {
  function main(arr) {
    // 防止无穷递归导致callstack溢出，也是将数组进行分解的终止条件
    if(arr.length <= 1) return arr // 返回arr
    // 将数组分割
    let mid = parseInt(arr.length / 2)
    let left = arr.slice(0, mid)
    let right = arr.slice(mid)
    // 开始递归调用
    return merge(main(left), main(right))
  }

  // 合并函数
  // left为左边的有序数组，li为left的指针
  // right为右边的有序数组，ri为right的指针
  function merge(left, right) {
    let li = 0,
        ri = 0,
        res = []
    // 终止条件：某一边的指针超出最后一个
    while(li < left.length && ri < right.length) {
      // 如果左边指针数值小于右边指针数值，往结果里push左边数值，同时左边指针+1(升序)
      if(left[li] < right[ri]) res.push(left[li++])
      // 反之亦然(可不考虑相等情况)
      else res.push(right[ri++])
      // else if(left[li] > right[ri]) res.push(right[ri++])
    }
    // 将未合并完的数组合并到result(有一边是一定合并完的)
    return res.concat(left.slice(li)).concat(right.slice(ri))
  }

  return main(arr)
}

let res = mergeSort([6, 7, 1, 4, 2, 3, 1])
console.log(res)

归并排序 ​

归并排序