JavaScript归并排序实现中的常见错误与优化实践

function mergesort(arr, left, right) {
    if (left < right) {
        let mid = parseInt((right - left) / 2) + left; // 问题1：效率较低的中间值计算
        mergesort(arr, left, mid);
        mergesort(arr, mid + 1, right); // 问题2：与后续merge函数的区间定义可能不一致
        merge(arr, left, mid, right);
    }
}

function merge(arr, left, mid, right) {
    let i = left, j = mid + 1, k = 0, temp = [];
    // 合并两个子数组到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++) { // 问题3：此循环在特定情况下是多余的
        temp[k] = arr[i];
        k++;
    }
    for (; j <= right; j++) { // 问题3：此循环在特定情况下是多余的
        temp[k] = arr[j];
        k++;
    }
    // 将temp数组复制回原数组arr
    for (let i = left; i <= right; i++) { // 核心问题：索引错误
        arr[i] = temp[i]; // 问题4：temp数组的索引k是从0开始，而arr的索引i是从left开始
    }
}

let arr = [ 5, 3, 7, 2, 9, 12, 4 ];
let n = arr.length;
mergesort(arr, 0, n); // 问题5：初始调用时right参数的语义不一致
console.log(arr); // 输出: [undefined, undefined, undefined, undefined, undefined, undefined, 3, 5]

/**
 * 归并排序函数
 * @param {Array} arr 待排序数组
 * @param {number} left 区间起始索引（包含）
 * @param {number} right 区间结束索引（不包含）
 */
function mergesort(arr, left, right) {
    // 当区间长度大于1时才需要排序
    if (right - left > 1) {
        // 计算中间索引，采用位运算，等同于 (left + right) / 2 并向下取整
        // 避免 (left + right) 溢出，同时保证在 left 和 right 之间
        let mid = left + ((right - left) >> 1);

        // 递归排序左半部分 [left, mid)
        mergesort(arr, left, mid);
        // 递归排序右半部分 [mid, right)
        mergesort(arr, mid, right);

        // 合并两个有序子数组
        merge(arr, left, mid, right);
    }
}

/**
 * 合并两个有序子数组
 * @param {Array} arr 原始数组
 * @param {number} left 第一个子数组的起始索引（包含）
 * @param {number} mid 第一个子数组的结束索引（不包含），也是第二个子数组的起始索引（包含）
 * @param {number} right 第二个子数组的结束索引（不包含）
 */
function merge(arr, left, mid, right) {
    let i = left;  // 左子数组的当前索引 [left, mid)
    let j = mid;   // 右子数组的当前索引 [mid, right)
    let k = 0;     // 临时数组的当前索引
    let temp = []; // 临时存储合并结果的数组

    // 比较两个子数组的元素，将较小的放入temp
    while (i < mid && j < right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++]; // 放入temp并递增索引
        } else {
            temp[k++] = arr[j++]; // 放入temp并递增索引
        }
    }

    // 将左子数组中剩余的元素复制到temp (如果存在)
    while (i < mid) {
        temp[k++] = arr[i++];
    }

    // 将右子数组中剩余的元素复制到temp (如果存在)
    // 注意：如果左子数组已处理完，这部分才可能执行
    // 实际上，这两个while循环只有一个会真正执行，因为另一个子数组已经处理完毕
    // 或者两者都执行，直到其中一个子数组耗尽
    // 采用 [left, right) 约定，此处的 j < right 是正确的
    // 并且不再需要额外的循环来处理剩余部分，因为上面的while循环已经处理了所有情况
    // 实际上，第二个 while 循环 (j < right) 在这种写法下是多余的，因为如果 i < mid 结束，j < right 必然成立，且 j 已经移动到正确位置
    // 但为了清晰，保留一个处理 j 的循环，虽然在实际运行时，如果 i 已经走完，j 对应的元素会直接被复制。
    while (j < right) { // 修正：此循环是必要的，确保右侧剩余元素也被复制
        temp[k++] = arr[j++];
    }

    // 将temp数组中的有序元素复制回原数组arr的对应区间
    for (let idx = 0; idx < k; idx++) {
        arr[left + idx] = temp[idx];
    }
}

// 示例用法
let arr = [ 5, 3, 7, 2, 9, 12, 4 ];
mergesort(arr, 0, arr.length); // 初始调用，right参数为数组长度，符合左闭右开约定
console.log(arr); // 输出: [2, 3, 4, 5, 7, 9, 12]