基于哨兵的C#归并排序实现输出异常问题排查

我帮你定位到了代码里的两个关键错误，正是它们导致了异常的输出结果：

错误1：左子数组填充时索引计算错误 #

在填充left数组的循环中，你直接使用arr[i]来取值，但这里的i是从0开始的，而左子数组的实际起始位置是lowerIndex，并非原数组的0索引。比如当递归处理后半段数组时，lowerIndex可能是3，这时候arr[i]会错误地取到原数组前几个位置的值，而不是目标子数组的元素。

修正方式：将赋值语句改为：

left[i] = arr[lowerIndex + i];

错误2：右子数组填充的双重错误 #

这段代码存在两个严重问题：

• 你把右子数组的元素错误地赋值给了left[j]，而不是right[j]，这不仅导致right数组始终是默认的0值，还覆盖了left数组的部分内容；
• 右子数组的起始位置应该是midIndex + 1，你当前的arr[midIndex + j]会从midIndex开始取值，包含了左子数组的最后一个元素，导致重复和错误。

修正方式：把循环里的代码改成：

right[j] = arr[midIndex + 1 + j];

修正后的完整Merge函数 #

void Merge(int[] arr, int midIndex, int lowerIndex, int upperIndex) {
    int leftArrayLength = midIndex - lowerIndex + 1;
    int rightArrayLength = upperIndex - midIndex;
    int[] left = new int[leftArrayLength + 1];
    int[] right = new int[rightArrayLength + 1];
    for (int i = 0; i < leftArrayLength; i++) {
        left[i] = arr[lowerIndex + i];
    }
    for (int j = 0; j < rightArrayLength; j++) {
        right[j] = arr[midIndex + 1 + j];
    }
    // Sentinels
    left[leftArrayLength] = int.MaxValue;
    right[rightArrayLength] = int.MaxValue;
    int m = 0;
    int n = 0;
    for (int k = lowerIndex; k <= upperIndex; k++) {
        if (left[m] <= right[n]) {
            arr[k] = left[m];
            m += 1;
        } else {
            arr[k] = right[n];
            n += 1;
        }
    }
}

修正后再运行你的归并排序，原数组{9, 8, 7, 6, 5, 4}会被正确排序为{4, 5, 6, 7, 8, 9}。

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