JavaScript归并排序实现中的常见陷阱与优化

// ... merge 函数内部
for (let i = left; i <= right; i++) {
    arr[i] = temp[i]; // 错误：直接使用 i 作为 temp 数组的索引
}

// ... merge 函数内部
// 假设 k 是 temp 数组中已填充元素的数量
for (let i = 0; i < k; i++) {
    arr[left + i] = temp[i]; // 正确：将 temp[0...k-1] 拷贝到 arr[left...left+k-1]
}

let mid = parseInt((right - left) / 2) + left; // 效率较低

let mid = left + ((right - left) >> 1); // 高效的整数除法

for (; i <= mid; i++) { // 拷贝左边剩余
    temp[k] = arr[i];
    k++;
}
for (; j <= right; j++) { // 拷贝右边剩余
    temp[k] = arr[j];
    k++;
}

function merge(arr, left, mid, right) {
    let i = left, j = mid, k = 0, temp = [];
    while (i < mid && j < right) { // 注意这里是 < mid 和 < right
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 拷贝左边剩余元素（如果存在）
    while (i < mid) {
        temp[k++] = arr[i++];
    }
    // 注意：这里不需要显式拷贝右边剩余元素。
    // 因为如果右边有剩余，意味着左边已全部拷贝，
    // 且右边的剩余元素在主 while 循环中已按序处理。
    // 如果左边有剩余，那么右边所有元素都已经参与了比较并进入了 temp 数组。
    // 也就是说，在主循环和上面的 while(i < mid) 结束后，
    // temp 数组中已经包含了所有应合并的元素。

    // 将 temp 数组的元素拷贝回 arr 的对应位置
    for (i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
}

/**
 * 归并排序主函数
 * @param {Array<number>} arr 要排序的数组
 * @param {number} left 子数组的起始索引 (包含)
 * @param {number} right 子数组的结束索引 (不包含)
 */
function mergesort(arr, left, right) {
    // 递归基准：当子数组长度小于等于1时，认为其已排序
    if (right - left > 1) {
        // 计算中间点，使用位运算进行高效整数除法
        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<number>} arr 原始数组
 * @param {number} left 左子数组的起始索引 (包含)
 * @param {number} mid 左子数组的结束索引 (不包含)，同时是右子数组的起始索引 (包含)
 * @param {number} right 右子数组的结束索引 (不包含)
 */
function merge(arr, left, mid, right) {
    let i = left;  // 左子数组的当前指针
    let j = mid;   // 右子数组的当前指针
    let k = 0;     // 临时数组的当前指针
    let temp = []; // 临时数组，用于存放合并后的元素

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

    // 将左子数组中剩余的元素（如果有）拷贝到 temp 数组
    // 此时，右子数组的元素要么已全部拷贝，要么在主循环中已处理完毕
    while (i < mid) {
        temp[k++] = arr[i++];
    }

    // 注意：这里不需要额外的循环来处理右子数组的剩余元素。
    // 因为如果在主循环中左子数组先耗尽，那么右子数组的剩余元素已经按照顺序
    // 放入了 temp 数组。如果右子数组先耗尽，那么上面 while(i < mid) 会处理左边剩余。

    // 将 temp 数组中的排序结果拷贝回原始数组的对应位置
    for (let index = 0; index < k; index++) {
        arr[left + index] = temp[index];
    }
}

// 示例用法
let arr = [5, 3, 7, 2, 9, 12, 4];
console.log("原始数组:", arr); // 原始数组: [5, 3, 7, 2, 9, 12, 4]

mergesort(arr, 0, arr.length); // 调用归并排序，right 参数为 arr.length
console.log("排序后数组:", arr); // 排序后数组: [2, 3, 4, 5, 7, 9, 12]