本文详解递归归并排序（mergesort）实现中因临时数组长度计算错误导致的越界、填充异常及输出混乱问题，并提供完整修正代码与关键原理说明。
本文详解递归归并排序（mergesort）实现中因临时数组长度计算错误导致的越界、填充异常及输出混乱问题，并提供完整修正代码与关键原理说明。
在您提供的 Java 递归归并排序实现中，核心逻辑（分治结构、合并流程）基本正确，但存在一个致命的数组边界错误，直接导致输出异常：前几项看似有序、中间出现多个 0、后续又混杂未排序元素——这并非递归失效，而是 merge 方法中临时数组 temp 的容量与拷贝逻辑不匹配所致。
? 根本问题：临时数组长度错误
原代码中：
int temp[] = new int[high + 1];
该语句创建了一个长度为 high + 1 的数组（例如当 low=0, high=6 时，temp 长度为 7），看似足够，实则严重错误：
-
merge操作仅处理子区间[low, high]（共high - low + 1个元素）； - 但
temp却按high + 1分配——若low > 0（如第二次递归调用mergesort(arr, 4, 6)），high=6仍分配长度为7的数组，而实际需容纳3个元素（索引 4~6）； - 更严重的是，后续拷贝语句：
for (int i = 0; i < temp.length; i++) { arr[i] = temp[i]; // ❌ 错误：将 temp[0..high] 强行覆盖 arr[0..high] }它无条件将整个
temp（长度high+1）写回arr的起始位置arr[0]开始，而非目标区间[low, high]！这会覆盖原数组前端有效数据，引入0（temp未赋值部分默认为0），并破坏已排序段。
✅ 正确修复方案
-
临时数组长度必须严格匹配待合并段长度：
int[] temp = new int[high - low + 1]; // ✅ 仅分配所需空间
-
合并结果应拷贝回原数组的对应区间
[low, high]，而非从arr[0]开始：// 将 temp 中 [0, temp.length-1] 的元素，拷贝到 arr[low] ~ arr[high] for (int i = 0; i < temp.length; i++) { arr[low + i] = temp[i]; // ✅ 关键修正：偏移量 low } 移除调试用的冗余打印（避免干扰逻辑验证）：
合并过程中的System.out.print(...)应删除或仅在调试时启用，否则输出混杂、难以定位问题。
? 完整修正代码（含注释）
import java.util.*;
public class Main {
public static void merge(int[] arr, int low, int mid, int high) {
// ✅ 正确：temp 长度 = 待合并元素总数
int[] temp = new int[high - low + 1];
int index = 0;
int left = low;
int right = mid + 1;
// 归并两个已排序子数组
while (left <= mid && right <= high) {
if (arr[left] <= arr[right]) {
temp[index++] = arr[left++];
} else {
temp[index++] = arr[right++];
}
}
// 复制剩余左半部分
while (left <= mid) {
temp[index++] = arr[left++];
}
// 复制剩余右半部分
while (right <= high) {
temp[index++] = arr[right++];
}
// ✅ 正确：将 temp 内容拷贝回 arr[low...high]
for (int i = 0; i < temp.length; i++) {
arr[low + i] = temp[i];
}
}
public static void mergesort(int[] arr, int low, int high) {
if (low >= high) return; // 基础情况：单元素或空区间
int mid = low + (high - low) / 2; // ✅ 防止整数溢出（推荐写法）
mergesort(arr, low, mid);
mergesort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
public static void main(String[] args) {
int[] arr = {2, 3, 46, 5, 8, 7, 6};
System.out.println("Original: " + Arrays.toString(arr));
mergesort(arr, 0, arr.length - 1);
System.out.println("Sorted: " + Arrays.toString(arr));
// 输出：Sorted: [2, 3, 5, 6, 7, 8, 46]
}
}⚠️ 注意事项与最佳实践
-
避免整数溢出：计算
mid时建议用low + (high - low) / 2替代(low + high) / 2，尤其在处理大数组时更安全。 -
空间局部性：
temp在每次merge中新建，虽简洁但非最优；生产环境可考虑复用全局临时数组以减少 GC 压力。 -
稳定性保证：当前实现中
if (arr[left] 使用 <code> 确保相等元素的相对顺序不变，维持归并排序的<strong>稳定性</strong>。 -
调试技巧：首次验证算法时，可添加日志打印
low,mid,high及合并前后的子数组片段，而非全数组输出，避免信息过载。
通过修正临时数组长度与拷贝范围，递归归并排序即可稳定、高效地完成全数组升序排序。理解“操作区间”与“内存布局”的严格对应关系，是编写正确分治算法的关键所在。
