今天要介绍的是归并排序，它相对复杂一点，但是性能更好，那他具体如何呢？废话少说，让我们来揭开它神秘的面纱。

归并排序

比前几章说到的排序性能要好，它是可以运用到实战里面的，火狐浏览器的 方法就是用的归并排序这个算法。

归并排序的思路

• 分：把数组劈成两半，在递归地对子数组进行 操作，直到分成一个个单独地数。

• 合：把两个数合并为有序数组，在对有序数组进行合并，直到全部子数组合并为一个完整数组。

合并两个有序数组

• 新建一个空数组 res，用于存放最终排序后地数组。

• 比较两个有序数组地头部，较小者出队并推入res中。

• 如果两个数组还有值，就重复第二步。

归并排序动画

• 首先我们可以发现一个颜色地数组变成五颜六色地。

• 说明完成了一轮递归操作，把来回数组劈成两半，直到变成一个个单独地数。

• 然后拿到两个单独地数，进行比对推入栈中，

• 在重复上一步

• 比对两个栈，推入

• 如此重复，比对出一个排序完整地栈

实现

代码如下：

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, arr.length)
        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
    }
    const res = rec(this)
    res.forEach((n, i) => { this[i] = n })
}
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
arr.mergeSort()
console.log(arr);
// [
   2,  3,  4,  5, 15, 19,
  26, 27, 36, 38, 44, 46,
  47, 48, 50
]

归并排序地时间复杂度

• 分地时间复杂度是 。

• 合地时间复杂度是 。

• 因为其是嵌套关系，所以总体地复杂度是 。

End~~~