本文详解归并排序中“部分排序”（非从索引0开始）时出现 arrayindexoutofboundsexception 的根本原因，并提供符合 java 惯用法的修正方案，涵盖边界定义、临时数组分配、循环条件调整等关键实践。
本文详解归并排序中“部分排序”（非从索引0开始）时出现 arrayindexoutofboundsexception 的根本原因，并提供符合 java 惯用法的修正方案，涵盖边界定义、临时数组分配、循环条件调整等关键实践。
归并排序在处理任意子区间（如 arr[3..7]）时失败，通常并非算法逻辑错误，而是边界约定不一致所致。原始代码采用“闭区间”语义（low 和 high 均为有效索引），但未严格保证 temp 数组容量覆盖 [low, high] 全范围，且递归调用中 mid + 1 可能越界——尤其当 low > 0 时，temp[i] 写入操作直接访问 temp 的非法下标。
✅ 推荐方案：采用左闭右开区间（[low, high)）
这是 Java 标准库（如 Arrays.sort(arr, from, to)）和多数现代实现采用的惯用约定：
- low 是起始索引（包含）
- high 是结束索引（不包含），即有效范围为 [low, high - 1]
- 顶层调用应传入 mergeSort(arr, temp, 0, arr.length)
该设计天然支持空区间（low >= high 时跳过）、避免 +1/-1 边界抖动，并使所有循环条件统一使用
以下是修正后的完整实现：
public static void mergeSort(int[] arr, int[] temp, int low, int high) {
if (high - low <= 1) return; // 空区间或单元素，无需排序
int mid = low + (high - low) / 2;
mergeSort(arr, temp, low, mid); // [low, mid)
mergeSort(arr, temp, mid, high); // [mid, high)
merge(arr, temp, low, mid, high); // 合并 [low, mid) 和 [mid, high)
}
public static void merge(int[] arr, int[] temp, int low, int mid, int high) {
// 复制 [low, high) 到 temp —— 注意：temp 必须长度 ≥ arr.length！
for (int i = low; i < high; i++) {
temp[i] = arr[i];
}
int i = low; // 左半区起点
int j = mid; // 右半区起点
int k = low; // 合并目标位置
// 合并两个有序段：[low, mid) 和 [mid, high)
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 中原位，无需复制（因 arr 和 temp 共享同一段内存视图）
}⚠️ 关键注意事项
- temp 数组必须与 arr 等长：即使只排序子区间，merge 中 temp[i] 访问的是原始索引位置（如 i=5），因此 temp 长度必须 >= arr.length。推荐初始化为 new int[arr.length]。
-
顶层调用务必校验参数：
if (from < 0 || to > arr.length || from > to) { throw new IllegalArgumentException("Invalid range: [" + from + ", " + to + ")"); } mergeSort(arr, temp, from, to); - 避免“魔法数字”：不要硬编码 mid + 1；统一使用 [low, mid) 和 [mid, high) 划分，逻辑清晰且可验证。
-
测试用例建议：
int[] a = {9, 5, 2, 8, 1, 7}; int[] t = new int[a.length]; mergeSort(a, t, 2, 5); // 仅排序索引 2~4（即 {2,8,1} → {1,2,8}） System.out.println(Arrays.toString(a)); // [9, 5, 1, 2, 8, 7]
采用左闭右开区间不仅修复了 ArrayIndexOutOfBoundsException，更提升了代码的健壮性、可读性与可维护性。在实现任何基于索引的分治算法时，明确并统一区间语义，是避免边界错误的第一道防线。
