5、归并排序

动图

代码

const mergeSort = arr => {
    //采用自上而下的递归方法
    const len = arr.length;
    if (len < 2) {
        return arr;
    }
    // length >> 1 和 Math.floor(len / 2) 等价
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle); // 拆分为两个子数组
    return merge(mergeSort(left), mergeSort(right));
};
const merge = (left, right) => {
    const result = [];
    while (left.length && right.length) {
        // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length) result.push(left.shift());
    while (right.length) result.push(right.shift());
    return result;
};
作者：天明夜尽
链接：https://juejin.im/post/6844903895789993997
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

https://juejin.im/post/6844903895789993997#heading-1