归并排序在Java中用数组实现需递归二分、排序子数组、合并，体现分治思想；空间开销主要来自合并的临时数组，非递归栈；核心三步为分（安全取中点）、治（子数组长度≤1时有序）、合（双指针合并后拷贝回原数组）。
在 Java 中用数组实现归并排序，核心是递归地将数组二分、排序子数组、再合并。它天然体现“分治”思想：分（Divide）→ 治（Conquer）→ 合（Combine）。空间开销主要来自合并时所需的临时数组，不是递归调用栈主导——这点常被误解。
分治结构：递归切分与有序合并
归并排序不原地排序，每次合并必须借助额外空间。整个过程可拆解为三步：
-
分：用
mid = left + (right - left) / 2安全取中点，递归处理[left, mid]和[mid+1, right] - 治：递归到底层（子数组长度 ≤ 1）自然有序，无需操作
- 合：用两个指针分别遍历左右子数组，将较小元素依次复制到临时数组；最后拷回原数组对应位置
关键代码：基于数组的自顶向下实现
以下是最简可用版本（含注释），避免对象创建和边界错误：
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int[] temp = new int[arr.length]; // 全局临时数组，复用减少GC
mergeSort(arr, temp, 0, arr.length - 1);
}
<p>private static void mergeSort(int[] arr, int[] temp, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, temp, left, mid); // 左半递归
mergeSort(arr, temp, mid + 1, right); // 右半递归
merge(arr, temp, left, mid, right); // 合并 [left, mid] 和 [mid+1, right]
}</p><p>private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
// 复制待合并段到 temp（只复制需要的部分）
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left, j = mid + 1, k = left;
// 双指针归并
while (i <= mid && j <= right) {
arr[k++] = (temp[i] <= temp[j]) ? temp[i++] : temp[j++];
}
// 拷贝剩余部分（只会执行其中一个）
while (i <= mid) arr[k++] = temp[i++];
while (j <= right) arr[k++] = temp[j++];
}</p>空间开销分析：O(n) 是主因，不是栈深度
很多人误以为递归深度 O(log n) 决定总空间，其实不然：
立即学习“Java免费学习笔记（深入）”；
-
临时数组：始终只分配
new int[arr.length]一份，大小恒为 n → 占用 O(n) - 递归栈：最大深度为树高 log₂n，每层仅存几个整型参数（left/mid/right），共约 O(log n) 空间
- 总空间复杂度：O(n) + O(log n) = O(n)，由临时数组主导
优化提示：复用同一份 temp 数组（如上所示），避免每次合并都新建，能显著减少 GC 压力。
为什么不能完全原地归并？
理论上存在 O(1) 额外空间的归并方案（如循环置换），但实现复杂、常数因子大、不稳定，且破坏“清晰分治”的教学意义。实际工程中，接受 O(n) 空间换 O(n log n) 稳定时间 是合理权衡。若内存极端受限，可考虑堆排序（O(1) 空间，但不稳定）或 TimSort（Java Arrays.sort() 对对象数组的默认实现，利用数据局部性优化）。
