Merge Sort条件语句触发数组越界错误的原因与解决方法

错误原因 #

1. 循环范围错误：你用Arr.length作为循环上限遍历整个原数组，但左右子数组的总长度仅等于原数组的目标区间长度（high-low+1）。当i超过左数组长度时，访问arr_left[i]会直接越界；i继续增大时，访问arr_right[i]也会超出它的长度。
2. 原数组索引计算错误：填充右子数组时，你用了Arr[mid + 1 + i]，当i取值较大时（比如i=4），mid+1+i=3+1+4=8，而原数组最大索引是7，直接触发数组越界。
3. 子数组索引错误：右子数组的索引应该从0开始递增，而非直接使用原数组的遍历变量i。比如当i=4时，右子数组长度只有4，最大索引为3，arr_right[4]必然越界。

修复方法 #

最直观的方式是拆分两个循环分别填充左右子数组，逻辑清晰且能彻底避免索引错误：

public static void merge(int[] Arr, int low, int mid, int high) {
    int[] arr_left = new int[mid - low + 1];
    int[] arr_right = new int[high - mid];
    
    // 填充左子数组：对应原数组low到mid区间
    for (int i = 0; i < arr_left.length; i++) {
        arr_left[i] = Arr[low + i];
    }
    
    // 填充右子数组：对应原数组mid+1到high区间
    for (int i = 0; i < arr_right.length; i++) {
        arr_right[i] = Arr[mid + 1 + i];
    }
    
    System.out.println(Arrays.toString(arr_left));
    System.out.println(Arrays.toString(arr_right));
}

替代实现方式 #

如果想用单个循环处理，可以用两个指针分别记录左右子数组的当前填充位置，遍历原数组的目标区间（low到high）而非整个数组：

public static void merge(int[] Arr, int low, int mid, int high) {
    int[] arr_left = new int[mid - low + 1];
    int[] arr_right = new int[high - mid];
    int leftIdx = 0, rightIdx = 0;
    
    for (int i = low; i <= high; i++) {
        if (i <= mid) {
            arr_left[leftIdx++] = Arr[i];
        } else {
            arr_right[rightIdx++] = Arr[i];
        }
    }
    
    System.out.println(Arrays.toString(arr_left));
    System.out.println(Arrays.toString(arr_right));
}

内容的提问来源于stack exchange，提问作者Phone Myat Thu