Java 归并排序深度解析
先说结论
归并排序是基于「分治思想」的排序算法，核心是先拆分、后合并，时间复杂度稳定为 O(nlogn)，且是稳定排序（相等元素相对位置不变），这两点是它比快排更受某些场景青睐的原因。
操作过程（两步核心）
- 拆分：把无序数组从中间拆分成左右两部分，递归拆分直到每个子数组只剩 1 个元素（单个元素天然有序）；
- 合并：把相邻的两个有序子数组，用双指针按大小顺序合并成一个新的有序数组，重复合并直到所有子数组合并为一个完整数组。
代价是需要额外 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 + ( - ) / =
拆为： 和 .以此类推 ↓
对半拆
↓ ↓
↓ ↓ ↓
