TypeScript实现归并排序结果丢失半数元素，求原因分析

问题根源 #

你的代码在拆分数组时出现了关键错误：

const second:number[] = mergeSort(arr.slice(half + 1));

Array.slice(start, end)的start参数表示截取的起始索引，当只传入一个参数时，会从该索引开始截取到数组末尾。你这里写了half + 1，会跳过索引为half的元素，递归拆分的每一层都会丢失一个元素，最终导致输出只剩原数组的半数元素。

正确的拆分逻辑应该是从half索引开始截取到数组末尾，无需加+1：

const second:number[] = mergeSort(arr.slice(half));

修复后的完整代码 #

function mergeSort(arr:number[]):number[]{
    if(arr.length <= 1){
        return arr;
    }

    const half:number = Math.floor(arr.length/2);
    const first:number[] = mergeSort(arr.slice(0,half));
    // 修复slice参数，去掉多余的+1
    const second:number[] = mergeSort(arr.slice(half));

    return merge(first, second);
}

function merge(a:number[], b:number[]):number[]{
    const c:number[] = [];
    while(a.length && b.length){
        if(a[0]<b[0]){
            c.push(a.shift()!);
        }else{
            c.push(b.shift()!);
        }
    }

    while(a.length){
        c.push(a.shift()!);
    }

    while(b.length){
        c.push(b.shift()!);
    }

    return c;
}

console.log(mergeSort([4, 53, 22, 10, 2, 74, 91, 33, 25, 14, 19, 100, 256, 81, 7, 300]));

验证结果 #

修复后运行代码，输出与预期完全一致：

[2, 4, 7, 10, 14, 19, 22, 25, 33, 53, 74, 81, 91, 100, 256, 300]

内容的提问来源于stack exchange，提问作者Bálint Réthy