拆分与合并的艺术·分治思想：Java归并排序深度解析

拆分与合并的艺术·分治思想：Java归并排序深度解析

面试高频 | 稳定排序 | 含过程演示 | 新手友好

先说结论

归并排序是基于「分治思想」的排序算法，核心是先拆分、后合并，时间复杂度稳定为 O(nlogn)，且是稳定排序（相等元素相对位置不变），这两点是它比快排更受某些场景青睐的原因。

操作过程（两步核心）

代价是需要额外 O(n) 的空间存放临时数组。

一、核心思想（用生活举例）

想象你是个老师，你有一摞试卷，你该怎么样使他的分数有序排列呢？

第一步：拆分（先拆小，拆到没法拆）
把50份试卷先分成两堆（25份+25份）→ 再把每堆拆成12+13份 → 继续拆…
直到每一堆都只剩1份试卷（单份试卷不用排序，天然“有序”）。

第二步：合并（再合大，合的时候排序）
把相邻的两小堆试卷合并：
– 比如先合“78分”和“85分”→ 排成[78,85]
– 再合“92分”和“88分”→ 排成[88,92]
– 接着合[78,85]和[88,92]→ 排成[78,85,88,92]

层层往上合并，每合并一次都按分数排好，最终所有试卷合成一大摞，就是有序的

二、过程演示

以 [8, 3, 9, 1, 7, 2, 5] 为例：

拆分阶段（递归往下）：

0 1 2 3 4 5 6 代表每个数对应的下标，mid = left + (right – left) / 2 = 0 + (6 – 0) / 2 = 3
[8, 3, 9, 1, 7, 2, 5] 拆为：[left, mid]和[mid + 1, right].以此类推
↓ 对半拆
[8, 3, 9, 1] [7, 2, 5]
↓ ↓
[8, 3] [9, 1] [7, 2] [5]
↓ ↓ ↓
[8][3] [9][1] [7][2]

每个子数组只剩1个元素，停止拆分。

合并阶段（从底层往上）：

[8][3] → 合并 → [3, 8]
[9][1] → 合并 → [1, 9]
[3,8]+[1,9] → 合并 → [1, 3, 8, 9]

[7][2] → 合并 → [2, 7]
[2,7]+[5] → 合并 → [2, 5, 7]

[1,3,8,9]+[2,5,7] → 合并 → [1, 2, 3, 5, 7, 8, 9] ✅

三、完整代码（含详细注释）

public class MergeSort {

public static void main(String[] args) {
int[] arr = {8, 3, 9, 1, 7, 2, 5};
mergeSort(arr);
System.out.println(Arrays.toString(arr));
// 输出：[1, 2, 3, 5, 7, 8, 9]
}

public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) return; // 空数组或单元素，不用排
int[] temp = new int[arr.length]; // 提前创建临时数组，避免每次合并都新建
sort(arr, 0, arr.length – 1, temp);
}

private static void sort(int[] arr, int left, int right, int[] temp) {
if (left >= right) return; // 子数组只剩1个元素，停止拆分

int mid = left + (right – left) / 2; // 防溢出写法，比 (left+right)/2 更安全
sort(arr, left, mid, temp); // 递归拆左半部分
sort(arr, mid + 1, right, temp); // 递归拆右半部分
merge(arr, left, mid, right, temp); // 左右都拆完，合并
}

private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 左子数组的指针，从 left 开始
int j = mid + 1; // 右子数组的指针，从 mid+1 开始
int k = left; // 临时数组的写入指针

// 双指针比较，小的先放进临时数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++]; // 用 <= 而不是 <，保证稳定性（相等时左边先放）
} else {
temp[k++] = arr[j++];
}
}

// 左边还有剩余，直接放入（右边已经用完）
while (i <= mid) temp[k++] = arr[i++];
// 右边还有剩余，直接放入（左边已经用完）
while (j <= right) temp[k++] = arr[j++];

// 把临时数组的结果写回原数组
for (int p = left; p <= right; p++) {
arr[p] = temp[p];
}
}
}

四、递归执行顺序（很多人卡在这里）

归并排序的递归顺序是：先把左边拆到底，再拆右边，拆完再合并，层层往上。

用代码对应一下：

sort(arr, left, mid, temp); // ① 先一路拆左边，拆到单个元素
sort(arr, mid + 1, right, temp); // ② 左边拆完，再拆右边
merge(arr, left, mid, right, temp); // ③ 左右都拆完，合并

不是"拆一层合一层"，而是"左边全部拆完 → 右边全部拆完 → 才开始合并"。

奇数个数组怎么拆？

[8, 3, 9, 1, 7] 长度5，mid = 0 + (4-0)/2 = 2
左：[8, 3, 9]（下标0-2）
右：[1, 7]（下标3-4）

mid 向下取整，左边可能比右边多一个，完全正常，递归会自动处理，不会出现 left > right。

五、面试高频问题

① 为什么终止条件是 left >= right 而不是 left == right？

正常递归只会触发 left == right，但写 >= 是防御性编程，防止代码写错时 left 意外超过 right 导致栈溢出。多一个等号，零性能损耗，规避极端 bug。

② 为什么 mid 用 left + (right – left) / 2？

防止整数溢出。当 left 和 right 都很大时，left + right 可能超过 Integer.MAX_VALUE，结果变成负数。先算差值再取中，完全安全。

③ 为什么归并排序是稳定的？

合并时用的是 arr[i] <= arr[j]，相等时优先放左边的元素，相等元素的相对顺序不变，所以稳定。

④ 归并 vs 快排，什么时候用哪个？

需要稳定排序（比如按多字段排序）用归并，其他情况快排更常用。

六、核心考点速查

作者：[识君啊]