归并排序Merge方法实现触发IndexOutOfRangeException的排查与解决

我在研读《算法导论》时尝试实现书中的归并排序（MergeSort）伪代码，但始终无法定位触发IndexOutOfRangeException的根源。

Merge方法 #

报错出现在left[i] < right[j]这一行

static void Merge(int[] array, int start, int middle, int end)
{
    i = 1;
    j = 1;

    for (k = start; k < end; k++)
    {
        if (left[i] < right[j])
        {
            array[k] = left[i];
            i = i + 1; // -> i++;
        }
        else
        {
            array[k] = right[j];
            j = j + 1; // -> j++;
        }
    }
}

越界原因分析 #

• 索引体系不匹配：《算法导论》的伪代码默认采用1起始索引逻辑，伪代码中i=1、j=1是对应1起始数组的访问规则，而C#等绝大多数编程语言的数组为0起始索引，直接照搬伪代码的初始值会导致访问left、right数组时直接跳过首个元素，若左/右子数组长度仅为1，会直接触发越界。
• 循环边界错位：伪代码中归并循环为for k = p to r（包含右边界r），如果传入的start、end已经是对齐0起始的数组索引，原代码中k < end的循环条件会漏掉最后一个元素的处理，若未做子数组遍历完成的边界判断，还会出现后续访问空索引的问题。
• 实现逻辑缺失：代码中未定义i、j、k的类型，也没有提前创建拆分用的left、right子数组，缺少子数组遍历完成后的兜底处理，也会引发额外异常。

问题解决 #

我通过将所有i和j变量的初始值设为0，将k的初始值调整为start - 1解决了该问题。

更通用的优化实现 #

如果不想偏移循环起始值，也可以按0起始索引的逻辑对齐调整：

• 拆分左子数组范围为array[start..middle]、右子数组为array[middle+1..end]，存入0起始的left、right数组
• 初始化i = 0、j = 0
• 循环条件改为k = start; k <= end; k++
• 增加兜底判断：当i遍历完左子数组时，直接填充右子数组剩余元素；当j遍历完右子数组时，直接填充左子数组剩余元素，无需依赖哨兵值即可避免越界。

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