Java实现归并排序出现ArrayIndexOutOfBoundException求助

你的代码里有三处关键错误导致了数组越界，逐一修正即可解决问题：

1. 左数组填充的索引错误 #

第一个for循环里的inputArr[p+i-1]会直接触发越界——当p=0（数组起始索引）且i=0时，计算出的索引是-1。左半区间是原数组的[p, q]范围，共n1=q-p+1个元素，正确的索引应该是p+i，刚好覆盖p到q的所有位置：

for(int i = 0; i < n1; i++)
    leftHalf[i] = inputArr[p+i];

2. 哨兵赋值的数组越界 #

leftHalf[n1+1]和rightHalf[n2+1]完全超出了数组的长度范围：你创建的leftHalf长度是n1，最大有效索引是n1-1。正确的做法是创建数组时多分配一个位置用于存放哨兵，再把哨兵赋值到数组的最后一位：

// 创建数组时多留一个位置存哨兵
int[] leftHalf = new int[n1 + 1];
int[] rightHalf = new int[n2 + 1];

// 填充数组逻辑...

// 哨兵赋值到数组最后一位
leftHalf[n1] = Integer.MAX_VALUE;
rightHalf[n2] = Integer.MAX_VALUE;

3. 合并循环的索引范围错误 #

最后一个for循环k < r会错误覆盖原数组的0到r-1位置，但我们要合并的是原数组中[p, r]的区间，所以k应该从p开始，到r结束：

for(int k = p; k <= r; k++) {
    if(leftHalf[i] <= rightHalf[j]){
        inputArr[k] = leftHalf[i];
        i++;
    }
    else {
        inputArr[k] = rightHalf[j];
        j++;
    }
}

修改后的完整merge方法 #

public static void merge(int[] inputArr, int p, int q, int r) {
    int n1 = q-p+1;
    int n2 = r-q;
    // 多分配一个位置存哨兵
    int[] leftHalf = new int[n1 + 1];
    int[] rightHalf = new int[n2 + 1];

    for(int i = 0; i < n1; i++)
        leftHalf[i] = inputArr[p+i];

    for(int i = 0; i < n2; i++)
        rightHalf[i] = inputArr[q+i+1]; // 这里补充修正：右半区间是[q+1, r]，所以应该是q+i+1

    leftHalf[n1] = Integer.MAX_VALUE;
    rightHalf[n2] = Integer.MAX_VALUE;

    int i = 0;
    int j = 0;

    for(int k = p; k <= r; k++) {
        if(leftHalf[i] <= rightHalf[j]){
            inputArr[k] = leftHalf[i];
            i++;
        }
        else {
            inputArr[k] = rightHalf[j];
            j++;
        }
    }
}

补充：右半区间填充时，原代码的inputArr[q+i]会包含q位置的元素（已经被左数组包含），所以应该改成inputArr[q+i+1]，确保右数组对应原数组的[q+1, r]区间。

调用merge_sort时，初始参数要传入数组的有效索引范围：merge_sort(inputArr, 0, inputArr.length - 1)

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