算法 - 归并排序

思路

• 分：把数组劈成两半，再递归对子数组进行“分”的操作，直至分成一个个单独的数
• 合：把两个数合并为有序数组，再对有序数组进行合并，直至全部子数组合并为一个完整数组
  （1）新建一个空数组res，用于存放最终的数组
  （2）比较两个有序数组的头部，较小者出队并推入res中
  （3）如果两个数组还有值，就重复第二步

Array.prototype.mergeSort = function () {
  const rec = (arr) => {
    if (arr.length === 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid)
    const orderLeft = rec(left)
    const orderRight = rec(right)
    const res = []
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else if (orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res;
  }
  rec(this)
}
const arr2 = [6, 8, 5, 9, 3, 2, 1]
const res = arr2.mergeSort()
console.log(res)

时间复杂度：O(nlogn)
空间复杂度：O(n)