使用mergeSort排序数组非起始段触发ArrayIndexOutOfBoundsException原因

当调用mergeSort对数组的非0起始片段排序时会触发ArrayIndexOutOfBoundsException，但排序从索引0开始的片段则正常运行，问题根源在于merge方法中对临时数组temp的索引处理逻辑。

问题代码 #

public static void mergeSort(int[] arr, int[] temp, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        
        mergeSort(arr, temp, low, mid);
        mergeSort(arr, temp, mid + 1, high);
        merge(arr, temp, low, mid, high);
    }
}

public static void merge(int[] arr, int[] temp, int low, int mid, int high) {

    for (int i = low; i <= high; i++) {
        temp[i] = arr[i];
    }
    
    int i = low;
    int j = mid + 1; 
    int k = low;
    
    while (i <= mid && j <= high) {
        if (temp[i] <= temp[j]) {
            arr[k] = temp[i];
            i++;
        } else {
            arr[k] = temp[j];
            j++;
        }
        k++;
    }
    while (i <= mid) {
        arr[k] = temp[i];
        i++;
        k++;
    }
}

原因分析 #

• merge方法的第一个循环直接使用原数组的索引i（从low到high）访问temp数组。
• 如果你为了节省内存，给temp传入的是仅对应排序片段长度的数组（比如排序arr[2..5]时，temp长度为4），那么temp[i]的索引i会超出temp的边界（temp索引仅到3，而i会取到5），触发越界异常。
• 当排序从0开始的片段时，i的范围是0到high，刚好和temp的索引范围匹配，所以不会出错。

修复方案 #

有两种可行的修复方式：

方式1：调整temp的索引偏移（推荐，节省内存）

修改merge方法，让temp的索引从0开始，对应排序片段的偏移量，避免直接使用原数组索引：

public static void merge(int[] arr, int[] temp, int low, int mid, int high) {
    int segmentLen = high - low + 1;
    // 将排序片段复制到temp的0到segmentLen-1位置
    for (int i = 0; i < segmentLen; i++) {
        temp[i] = arr[low + i];
    }
    
    int i = 0; // temp左半段起始索引
    int j = mid - low + 1; // temp右半段起始索引
    int k = low; // arr的目标起始索引
    
    while (i <= mid - low && j < segmentLen) {
        if (temp[i] <= temp[j]) {
            arr[k] = temp[i];
            i++;
        } else {
            arr[k] = temp[j];
            j++;
        }
        k++;
    }
    // 复制剩余的左半段元素
    while (i <= mid - low) {
        arr[k] = temp[i];
        i++;
        k++;
    }
}

方式2：让temp长度与原数组一致

调用mergeSort时，传入一个和arr长度完全相同的temp数组，这样直接使用原数组索引访问temp也不会越界，但会浪费部分内存（如果仅排序小片段）。

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