js归并排序的实现

归并排序采用的是分治的思想，首先是“分”，将一个数组反复二分为两个小数组，直到每个数组只有一个元素；其次是“治”，从最小数组开始，两两按大小顺序合并，直到并为原始数组大小，下面是图解：

分”就是将原始数组逐次二分，直到每个数组只剩一个元素，一个元素的数组自然是有序的，所以就可以开始“治”的过程了。

时间复杂度分析：分的过程需要三步：log8 = 3，而每一步都需要遍历一次8个元素，所以8个元素共需要运行 8log8 次指令，那么对于 n 个元素，时间复杂度为 O(nlogn)。

“治”实际上是将已经有序的数组合并为更大的有序数组。那怎么做呢?就是创建一个新数组，比较left[0]和right[0] ，那个比较小就将那个的值放进新数组，然后再继续比较left[0]和right[1]，或者是left[1]和right[0]。可以看出数组left，right都只需遍历一遍，所以对两个有序数组的排序的时间复杂度为O(n)。

一、递归分解

二、合并为有序数组

三、js代码实现

function mergeSort (arr) {
    let len = arr.length
    if (len < 2) {
        return arr
    }
    let middle = Math.floor(len/2)
    //拆分成两个子数组
    let left =  arr.slice(0, middle)
    let right = arr.slice(middle,len)
    //递归拆分
    let mergeSortLeft = mergeSort(left)
    let mergeSortRight = mergeSort(right)
    //合并
    return merge( mergeSortLeft,mergeSortRight)
}
const merge = (left, right) => {
    const result = [];

    while (left.length && right.length) {
        // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
        if (left[0] <= right[0]) {
            result.push(left.shift()); //每次都要删除left或者right的第一个元素，将其加入result中
        } else {
            result.push(right.shift());
        }
    }
    //将剩下的元素加上
    while (left.length) result.push(left.shift());

    while (right.length) result.push(right.shift());

    return result;
};

图解来源：https://www.jianshu.com/p/33cffa1ce613

js归并排序的实现

推荐阅读