本文详解如何在 Java 归并排序中正确处理数组引用与返回值，解决因忽略原数组更新导致的“排序无效”问题——关键在于 merge() 方法必须将合并结果写回原始输入数组，而非仅返回新数组。
本文详解如何在 java 归并排序中正确处理数组引用与返回值，解决因忽略原数组更新导致的“排序无效”问题——关键在于 `merge()` 方法必须将合并结果写回原始输入数组，而非仅返回新数组。
在标准的自顶向下归并排序实现中，sort() 通常作为入口方法，调用递归的 mergesort()，后者再调用 merge() 合并已排序的左右子数组。然而，您当前代码的核心缺陷在于：mergesort() 虽接收原始数组 a，但其内部递归调用 mergesort(leftArray) 和 mergesort(rightArray) 返回的是全新数组，而最终 merge(leftArray, rightArray) 也返回一个全新数组——该结果未被写回原始 a 的任何位置，导致 sort() 方法执行完毕后，传入的原始数组 a 仍保持未变。
换句话说：您的 merge() 方法逻辑完全正确（输出 "MERGE: A E E L M O P R S T X" 已验证），但它返回的新数组 array 在 mergesort() 中被直接丢弃，原始参数 a 始终未被修改。
✅ 正确做法：让 merge() 执行原地写入
应将 merge() 改为 void 方法，并接受目标数组 dest 及起始索引 lo（或直接复用原始 a 作为目标），确保合并结果直接覆盖原始待排序区域。以下是符合接口约束且修复逻辑的重构方案：
@Override
public void sort(Comparable[] a) {
if (a == null || a.length <= 1) return;
// 创建临时辅助数组，避免每次 merge 都新建
Comparable[] aux = new Comparable[a.length];
mergesort(a, aux, 0, a.length - 1);
}
@Override
public void mergesort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergesort(a, aux, lo, mid); // 排序左半部分
mergesort(a, aux, mid + 1, hi); // 排序右半部分
merge(a, aux, lo, mid, hi); // 将 [lo, mid] 和 [mid+1, hi] 合并到 a[lo..hi]
}
@Override
public void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// 将 a[lo..hi] 复制到 aux[lo..hi]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++]; // 左半部分已耗尽
else if (j > hi) a[k] = aux[i++]; // 右半部分已耗尽
else if (less(aux[i], aux[j])) a[k] = aux[i++]; // 取较小者
else a[k] = aux[j++];
}
}? 关键变更说明：
立即学习“Java免费学习笔记（深入）”；
- mergesort() 和 merge() 均改为 void，不再返回数组；
- 引入辅助数组 aux 一次性分配，提升性能；
- merge() 明确操作范围 [lo, mid] 和 [mid+1, hi]，并将结果直接写入原始数组 a 的对应位置；
- sort() 内部调用 mergesort(...) 后，a 即为完全排序后的结果。
⚠️ 注意事项与常见误区
- 不要混淆“返回新数组”与“就地排序”：题目要求 sort(Comparable[] a) 方法对 a 本身完成排序（即副作用），因此所有中间操作必须最终反映在 a 上。
- 避免无意义的对象创建：原代码中 leftArray/rightArray 频繁新建，不仅低效，更易引发引用混乱；使用索引分治 + 辅助数组是经典解法。
- less() 方法需确保稳定性：若 a[i].compareTo(a[j])
- 边界检查不可省略：lo >= hi 是递归终止条件，i > mid 和 j > hi 是合并循环中的安全守卫。
✅ 验证示例
输入：Comparable[] a = {"S","O","R","T","E","X","A","M","P","L","E"};
调用 sort(a) 后，a 将变为：{"A","E","E","L","M","O","P","R","S","T","X"} —— 完全符合预期。
归并排序的本质是“分而治之 + 有序合并”，而保证结果落回原始容器，是工程实现中不可忽视的契约细节。遵循上述结构，即可写出健壮、高效、符合接口规范的 Java 归并排序实现。
