归并排序子数组越界问题解析

本文直击归并排序在处理任意子数组（如arr[3..7]）时频繁崩溃的痛点，深入剖析ArrayIndexOutOfBoundsException背后的本质原因——错误采用“左闭右闭”区间约定导致temp数组越界和递归分割失衡，并果断推荐更安全、更符合Java生态的“左闭右开”区间设计（[low, high)），配以清晰修正代码和关键实现细节，助你写出健壮、可维护、零越界的归并排序。

本文深入解析归并排序在对非起始索引子数组（如 arr[3..7]）进行排序时触发 ArrayIndexOutOfBoundsException 的根本原因，并提供符合 Java 惯用法的、边界安全的递归实现方案。

本文深入解析归并排序在对非起始索引子数组（如 arr[3..7]）进行排序时触发 `ArrayIndexOutOfBoundsException` 的根本原因，并提供符合 Java 惯用法的、边界安全的递归实现方案。

归并排序的健壮性高度依赖于对子数组边界的精确理解与一致约定。原始代码中，high 参数被定义为待排序区间的最后一个有效索引（inclusive），即区间为 [low, high]。这一约定看似直观，却在实践中埋下两大隐患：

1. temp 数组索引越界：merge 方法中执行 temp[i] = arr[i]（i 从 low 到 high），要求 temp 数组长度至少为 high + 1；但若 low > 0（例如 low=3, high=7），而 temp 仅按 arr.length 分配（即 temp[0..arr.length-1]），则 temp[7] 合法，但 temp[3] 到 temp[7] 的写入本身无越界——真正问题在于递归调用中 mid+1 可能超出 temp 容量上限（见后文分析）；
2. 递归终止与分割逻辑错位：原终止条件 if (low < high) 在 low == high 时停止，看似合理；但当 low > 0 时，mid = low + (high - low) / 2 计算正确，而 mergeSort(arr, temp, mid + 1, high) 中 mid + 1 可能等于 high + 1（例如 low=5, high=5 → mid=5 → mid+1=6），导致后续 temp[j]（j = mid + 1 = 6）访问 temp[6]，而 temp 长度仅为 arr.length（假设 arr.length=6，索引最大为 5），从而抛出 ArrayIndexOutOfBoundsException。

更本质的问题是：将 high 定义为 inclusive 索引，破坏了“左闭右开”（[low, high)）这一在 Java 集合操作（如 Arrays.copyOfRange, List.subList）中广泛采用的、更安全且可组合的区间约定。它无法自然表达空区间（low == high 即为空），且使边界计算易出错。

✅ 推荐解决方案：采用 左闭右开区间 [low, high)

• high 表示第一个不参与排序的元素索引（exclusive）；
• 顶层调用应传入 mergeSort(arr, temp, 0, arr.length)；
• temp 数组必须与 arr 等长（new int[arr.length]），确保所有可能访问的索引 i ∈ [low, high) 均在 temp 合法范围内。

以下是修正后的完整实现：

public static void mergeSort(int[] arr, int[] temp, int low, int high) {
    // 终止条件：区间长度 <= 1（即 high - low <= 1）
    if (high - low <= 1) {
        return;
    }

    int mid = low + (high - low) / 2; // mid 是右半区起点，满足 [low, mid) 和 [mid, high)
    mergeSort(arr, temp, low, mid);     // 左半区：[low, mid)
    mergeSort(arr, temp, mid, high);    // 右半区：[mid, high)
    merge(arr, temp, low, mid, high);   // 合并 [low, mid) 和 [mid, high) → [low, high)
}

public static void merge(int[] arr, int[] temp, int low, int mid, int high) {
    // 复制 [low, high) 范围到 temp（注意：i < high）
    for (int i = low; i < high; i++) {
        temp[i] = arr[i];
    }

    int i = low;      // 左半区当前索引（[low, mid)）
    int j = mid;      // 右半区当前索引（[mid, high)）
    int k = low;      // 合并结果写入 arr 的起始位置

    // 合并两个有序子段
    while (i < mid && j < high) {
        if (temp[i] <= temp[j]) {
            arr[k++] = temp[i++];
        } else {
            arr[k++] = temp[j++];
        }
    }

    // 复制左半区剩余元素
    while (i < mid) {
        arr[k++] = temp[i++];
    }

    // 注意：右半区剩余元素无需复制，因它们已在 arr 中对应位置（但为完备性可保留）
    // while (j < high) { arr[k++] = temp[j++]; }
}

? 关键注意事项：

• temp 数组分配：务必使用 int[] temp = new int[arr.length];。即使只排序子数组，temp 仍需覆盖整个 arr 的索引空间，因为 merge 中 temp[i] 的 i 可达 high-1，而 high 最大为 arr.length。
• 顶层调用规范：排序整个数组 → mergeSort(arr, temp, 0, arr.length)；排序子数组 arr[3..7]（含索引 3,4,5,6,7 共 5 个元素）→ mergeSort(arr, temp, 3, 8)。
• 空区间安全：当 low >= high 时，high - low <= 0，直接返回，天然支持空操作。
• 性能无损：该修改未增加额外时间或空间复杂度，仍保持 O(n log n) 时间与 O(n) 空间。

总结：归并排序的区间约定不是语法细节，而是决定算法鲁棒性的设计基石。拥抱 [low, high) 惯例，不仅能彻底规避索引越界，更能提升代码可读性、可测试性与与其他 Java API 的互操作性。

理论要掌握，实操不能落！以上关于《归并排序子数组越界问题解析》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！