SOURCE

// 合并两个有序数组
function merge(left, right) {
    // 这个时候 left、right 都已经是有序的了
    const result = [];
    // 左右数组的都不为空的情况
    while (left.length && right.length) {
        const [leftMin, ...leftOthers] = left;
        const [rightMin, ...rightOthers] = right;
        if (leftMin <= rightMin) {
            result.push(leftMin);
            left = [...leftOthers];
        } else {
            result.push(rightMin);
            right = [...rightOthers];
        }
    }
    // 其中一个数组为空的情况
    while (left.length) {
        const [leftMin, ...leftOthers] = left;
        result.push(leftMin);
        left = [...leftOthers];
    }

    while (right.length) {
        const [rightMin, ...rightOthers] = right;
        result.push(rightMin);
        right = [...rightOthers];
    }
    return result;
}

/**
 * @Desc 返回一个有序数组
*/
function mergeSort(arr) {
    // 递归的出口：当数组的长度为1的时候，我们认为这个数组已经是有序的了
    if (arr.length <= 1) {
        return arr;
    }
    // 
    const mid = Math.floor(arr.length / 2);
    // step1: 首先，将待排序数拆分成 left 和 right 两个数组
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);

    // step2: 将左、右数组分别做排序（也就是mergeSort要么返回数组长度为1的数组，
    // 或者是经过merge合并过后的有序数组）
    let mergedLeftArr = mergeSort(left);
    let mergedRightArr = mergeSort(right);

    // step3: 将有序数组进行合并
    return merge(mergedLeftArr, mergedRightArr);
}

console.log('[2, 9, 6, 7, 4, 3, 1, 8]', mergeSort([2, 9, 6, 7, 4, 3, 1, 8]))