归并排序 JavaScript

// 归并排序
function merge(left, right) {
    let arr = [];
    // 此条件代表当有一个数组为空之后，则停止循环
    while (left.length && right.length) {
        // 从左右子数组的最小元素中选择较小的元素 push 到 arr
        if (left[0] > right[0]) {
            arr.push(right.shift());
        } else {
            arr.push(left.shift());
        }
    }
    console.log("arr", arr);
    // 输出的数组要加上 left 或 right 剩下的值，由于每次都 push 最小值，则剩余的一定是大值，所以 push 到最后
    // 由于 left 和 right length 可能为相等或相差 1，所以这里 left 和 right 不分先后
    return [...arr, ...left, ...right];
}
function mergeSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    const half = arr.length / 2;
    const left = arr.splice(0, half);
    const right = arr;
    return merge(mergeSort(left), mergeSort(right));
}

console.log(mergeSort([4, 8, 7, 2, 11, 1, 3]))