本文深入解析归并排序在对非起始索引子数组（如 arr[3..7]）进行排序时触发 ArrayIndexOutOfBoundsException 的根本原因，并提供符合 Java 惯用法的、边界安全的递归实现方案。
本文深入解析归并排序在对非起始索引子数组（如 arr[3..7]）进行排序时触发 `arrayindexoutofboundsexception` 的根本原因，并提供符合 java 惯用法的、边界安全的递归实现方案。
归并排序的健壮性高度依赖于对子数组边界的精确理解与一致约定。原始代码中，high 参数被定义为待排序区间的最后一个有效索引（inclusive），即区间为 [low, high]。这一约定看似直观，却在实践中埋下两大隐患：
- 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 容量上限（见后文分析）；
- 递归终止与分割逻辑错位：原终止条件 if (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 合法范围内。
以下是修正后的完整实现：
立即学习“Java免费学习笔记（深入）”；
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
- 性能无损：该修改未增加额外时间或空间复杂度，仍保持 O(n log n) 时间与 O(n) 空间。
总结：归并排序的区间约定不是语法细节，而是决定算法鲁棒性的设计基石。拥抱 [low, high) 惯例，不仅能彻底规避索引越界，更能提升代码可读性、可测试性与与其他 Java API 的互操作性。
