JavaScript - 排序算法 - 归并排序

特点：

• 时间复杂度：O(nlog2n)
• 归并排序是稳定的排序算法

原理：（分治法）

• 原理类似于合并两条有序链表
• 分割为多条小的有序队列，通过两两合并最终实现完整序列

代码实现：（递归）

// 采用自上而下的递归方法
function mergeSort(arr) {  
    const len = arr.length;
    if (len < 2) return arr;
    const middle = Math.floor(len >> 1);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
    let 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;
}