请求排查归并排序代码中的Bug并解释异常输出原因

1. 排序调用的边界参数错误 #

原代码调用mergesort(arr, 0, n)时，n是数组长度（7），但数组的有效索引范围是0到n-1（即0到6）。传入right = 7会让递归过程处理超出数组实际范围的索引，导致数组被自动扩展，最终出现多个undefined值。

修复方式：调用时传入n-1作为右边界：

mergesort(arr, 0, n - 1);

2. 临时数组的索引映射错误 #

merge函数最后将临时数组temp的值复制回原数组时，代码写的是：

for (let i = left; i <= right; i++) {
    arr[i] = temp[i];
}

但temp是从索引0开始填充的，长度只有right - left + 1。当left > 0时，temp[i]会访问到temp中不存在的索引，返回undefined，直接覆盖原数组的正确值。

修复方式：把temp的索引偏移为i - left，对应temp的起始索引0：

for (let i = left; i <= right; i++) {
    arr[i] = temp[i - left];
}

修复后的完整代码 #

function mergesort(arr, left, right) {
    if (left < right) {
        let mid = parseInt((right - left) / 2) + left;
        mergesort(arr, left, mid);
        mergesort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

function merge(arr, left, mid, right) {
    let i = left, j = mid + 1, k = 0, temp = [];
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k] = arr[i];
            i++;
            k++;
        } else {
            temp[k] = arr[j];
            j++;
            k++;
        }
    }
    for (; i <= mid; i++) {
        temp[k] = arr[i];
        k++;
    }
    for (; j <= right; j++) {
        temp[k] = arr[j];
        k++;
    }
    // 修复索引映射问题
    for (let i = left; i <= right; i++) {
        arr[i] = temp[i - left];
    }
}

let arr = [5, 3, 7, 2, 9, 12, 4];
n = arr.length;
// 修复右边界参数
mergesort(arr, 0, n - 1);
console.log(arr); // 输出: [2, 3, 4, 5, 7, 9, 12]

内容的提问来源于stack exchange，提问作者Hasibul Alam