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

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]; // 错误：这里应该是temp[i - left]或使用单独的索引
    }
}

let arr = [ 5, 3, 7, 2, 9, 12, 4 ];
n = arr.length;
mergesort(arr, 0, n); // 问题所在：right参数通常指最后一个元素的索引，而不是数组长度

for (let i = left; i <= right; i++) {
    arr[i] = temp[i]; // 错误！temp[i]可能越界或取到错误的值
}

for (let idx = 0; idx < k; idx++) {
    arr[left + idx] = temp[idx];
}

let mid = left + ((right - left) >> 1); // 等同于 Math.floor((right - left) / 2) + left

for (; i <= mid; i++) {
    temp[k] = arr[i];
    k++;
}
for (; j <= right; j++) {
    temp[k] = arr[j];
    k++;
}

/**
 * 归并排序主函数
 * @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
    // 注意：如果left子数组已经全部拷贝完，那么right子数组剩余的元素会直接拷贝。
    // 如果right子数组已经全部拷贝完，那么这个循环不会执行。
    while (j < right) { // 也可以写成 for (; j < right; j++) { temp[k++] = arr[j]; }
        temp[k++] = arr[j++];
    }

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

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

mergesort(data, 0, data.length); // 初始调用时，right为数组长度
console.log("排序后数组:", data); // 输出: 排序后数组: [2, 3, 4, 5, 7, 9, 12]

let emptyArr = [];
mergesort(emptyArr, 0, emptyArr.length);
console.log("空数组排序后:", emptyArr); // 输出: 空数组排序后: []

let singleArr = [42];
mergesort(singleArr, 0, singleArr.length);
console.log("单元素数组排序后:", singleArr); // 输出: 单元素数组排序后: [42]