
本文详解 java 中 merge sort 的常见实现缺陷——合并后未将排序结果写回原数组,导致输出混乱;通过补全元素回填逻辑,即可获得正确排序结果。
本文详解 java 中 merge sort 的常见实现缺陷——合并后未将排序结果写回原数组,导致输出混乱;通过补全元素回填逻辑,即可获得正确排序结果。
你的 Merge Sort 实现逻辑整体是正确的:分治结构清晰,Merge 函数中双指针归并、边界处理(剩余左/右半段)也都无误。问题根源在于——你创建了临时有序列表 new_list,却从未将其内容复制回原数组 arr 的对应区间。因此,每次 Merge 虽然打印出看似“局部有序”的序列,但这些数据并未影响后续递归调用所依赖的 arr 状态,导致上层归并始终基于未更新的原始数据,最终输出完全错乱。
✅ 正确做法:在 Merge 末尾回填结果
只需在 Merge 方法最后、打印语句之后,添加一段将 new_list 中元素按顺序写回 arr[low...high] 的代码:
// 在 Merge 方法末尾(print 之后)添加:
for (int i = 0; i < new_list.size(); i++) {
arr.set(low + i, new_list.get(i));
}该循环确保 arr 从索引 low 开始的连续 new_list.size() 个位置被正确覆盖,使本次归并的成果真正生效,为上层递归提供准确的子数组状态。
? 完整修正后的 Merge 方法(关键修改已高亮)
public static void Merge(ArrayList<Integer> arr, int low, int mid, int high) {
int left = low;
int rightPointer = mid + 1;
ArrayList<Integer> new_list = new ArrayList<>();
// 归并主逻辑(保持不变)
while (left <= mid && rightPointer <= high) {
if (arr.get(left) <= arr.get(rightPointer)) {
new_list.add(arr.get(left));
left++;
} else {
new_list.add(arr.get(rightPointer));
rightPointer++;
}
}
// 处理左半段剩余
while (left <= mid) {
new_list.add(arr.get(left));
left++;
}
// 处理右半段剩余
while (rightPointer <= high) {
new_list.add(arr.get(rightPointer));
rightPointer++;
}
// ✅ 关键修复:将归并结果写回原数组对应区间
for (int i = 0; i < new_list.size(); i++) {
arr.set(low + i, new_list.get(i));
}
// (可选)调试打印:此时 arr[low..high] 已真实有序
System.out.print("Merged [" + low + "," + high + "]: ");
for (int ele : new_list) {
System.out.print(ele + " ");
}
System.out.println();
}⚠️ 注意事项与最佳实践
-
不要依赖打印判断正确性:你当前的
System.out.print仅反映new_list内容,而非arr真实状态。调试时建议在MergeSort结束后统一打印arr全局状态。 -
避免重复创建 ArrayList:高频调用下,可考虑复用
ArrayList或使用普通数组提升性能(如int[] temp = new int[high - low + 1])。 -
边界安全:
mid = (low + high) / 2在int范围内是安全的,但若处理超大数组,建议改用mid = low + (high - low) / 2防溢出(本例无需)。 -
最终验证:修正后运行,
main中list将输出升序结果:[3, 5, 8, 10, 10, 14, 18, 22, 24, 25, 29, 35, 42, 50, 50]
归并排序的精髓不仅在于“分”与“并”,更在于并后结果必须持久化到原结构。这一步缺失,整个算法便失去自底向上的累积效应。补上回填逻辑,你就真正打通了 Merge Sort 的完整闭环。

















