Java实现归并排序抛出ArrayIndexOutOfBoundsException异常排查

报错信息 #

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1

错误原因定位 #

代码共有3处逻辑错误，共同触发索引越界：

• 右边界取值逻辑矛盾：初始调用mergesortalgorithm时传入的右边界是arr.length，但Java数组合法索引范围是0到arr.length-1，后续所有循环、递归判断都用<=ub作为边界条件，会直接访问数组不存在的索引位。
• 临时数组长度计算错误：合并逻辑里临时数组长度写为lb + ub，实际当前待合并的区间元素总数是ub - lb + 1，lb+ub计算出的长度完全不符合当前区间大小，要么浪费空间要么长度不足触发越界。
• 元素拷回逻辑索引错位：临时数组从下标0开始存储合并后的有序元素，但拷回原数组时直接用原数组的下标l访问临时数组，既跳过了临时数组的有效存储位，又会访问到临时数组未分配的索引位置。

修正后可运行代码 #

import java.util.Arrays;

public class Sorting {

    public static void main(String[] args) {
        int[] arr = {5,3,4,7,2,8,6,9,1};
        mergesort(arr);
    }

    static void mergesort(int[] arr){
        // 右边界传数组最大合法索引arr.length-1
        mergesortalgorithm(arr,0, arr.length-1);
        System.out.println("The sorted array is :" + Arrays.toString(arr));
    }

    static void mergesortalgorithm(int[] arr,int lb,int ub){
        if (lb < ub){
            int mid = (lb + ub)/2;
            mergesortalgorithm(arr,lb,mid);
            mergesortalgorithm(arr,mid + 1,ub);
            merge(arr,lb,mid,ub);
        }
    }

    static void merge(int[] arr,int lb,int mid,int ub){
        int i = lb;
        int j = mid + 1;
        int k = 0;
        // 临时数组长度匹配当前合并区间的元素总数
        int[] newarray = new int[ub - lb + 1];
        while (i <= mid && j <= ub){
            if (arr[i] <= arr[j]){
                newarray[k] = arr[i];
                i++;
            }
            else {
                newarray[k] = arr[j];
                j++;
            }
            k++;
        }
        if (i > mid){
            while (j <= ub){
                newarray[k] = arr[j];
                j++;
                k++;
            }
        }
        else {
            while (i <= mid){
                newarray[k] = arr[i];
                i++;
                k++;
            }
        }
        // 拷回时临时数组从0位开始取，对应原数组lb位置开始写入
        for (int l = 0;l < newarray.length;l++){
            arr[lb + l] = newarray[l];
        }
    }
}

修正后运行输出结果：
The sorted array is :[1, 2, 3, 4, 5, 6, 7, 8, 9]

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