先把数组拆到只剩一个数（天然有序），再两两合并——合并两个有序数组，比想象中简单得多。
如果有两个已经排好序的数组，把它们合并成一个更大的有序数组，其实是一件很简单的事——完全不需要重新排序，只要拿两根手指分别指着两个数组的开头，每次比较手指指到的两个数，把较小的那个拿出来放进新数组，对应的手指往后挪一位，一直重复，直到其中一个数组被"掏空"，另一个数组剩下的部分直接整体接到后面就行了。
归并排序的思路，就是把这个"合并两个有序数组"的简单操作反复利用起来：先把原数组一路拆成一个个只有 1 个元素的小段——只有 1 个元素当然天然有序——再把相邻的小段两两合并成有序的大段，合并出来的大段再两两合并……一层一层往上合，直到合并成整个有序数组。
在学拆分之前，先把最核心的"合并"操作单独看清楚。假设已经有两个排好序的小数组 [2, 5, 8] 和 [1, 3, 9]，要把它们合并成一个有序数组：
5、8 整体接上去之后，别忘了右边其实还有一个 9 尚未处理——只是这一步右边恰好先用完了，所以看不到它被"接上"的过程。完整走完的话，最终结果应该是 1 2 3 5 8 9。这里想强调的是：不管是哪一边先用完，另一边剩下的所有元素都必须原样整体接到结果末尾，一个都不能漏，下面的代码和陷阱里会再强调一次。O(n) 操作。这也是归并排序效率的关键所在。有了"合并"这个工具，剩下的问题就是：怎么才能拿到两个"已经排好序"的小数组？答案是递归地拆——不断把数组从中间切成两半，直到每一段都只剩 1 个元素（1 个元素当然已经是"有序"的），再把这些最小的段两两合并、逐层往上，最终合并回整个数组。用数组 [5, 2, 8, 1, 9, 3] 演示完整过程：
3 层（log₂6 ≈ 2.6，向上取整是 3 层），每层合并的总工作量都是 O(n)，所以整体是 O(n log n)。| 1 | int temp[100005]; // 合并时用的临时数组，大小要开够 |
| 2 | |
| 3 | void Merge(int arr[], int left, int mid, int right) |
| 4 | { |
| 5 | int i = left, j = mid + 1, k = left; // i管左段，j管右段，k管临时数组的位置 |
| 6 | |
| 7 | while (i <= mid && j <= right) // 两段都还有元素没比完 |
| 8 | { |
| 9 | if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } // 左边小，拿左边 |
| 10 | else { temp[k++] = arr[j++]; } // 右边小，拿右边 |
| 11 | } |
| 12 | |
| 13 | while (i <= mid) { temp[k++] = arr[i++]; } // 左段还剩的，整体接上（不能漏！） |
| 14 | while (j <= right) { temp[k++] = arr[j++]; } // 右段还剩的，整体接上（不能漏！） |
| 15 | |
| 16 | for (int x = left; x <= right; x++) |
| 17 | { |
| 18 | arr[x] = temp[x]; // 把排好的结果从临时数组写回原数组 |
| 19 | } |
| 20 | } |
| 21 | |
| 22 | void MergeSort(int arr[], int left, int right) |
| 23 | { |
| 24 | if (left >= right) return; // 递归终止：只剩 0 或 1 个元素，天然有序 |
| 25 | |
| 26 | int mid = (left + right) / 2; // 从中间切一刀 |
| 27 | MergeSort(arr, left, mid); // 递归排左半段 |
| 28 | MergeSort(arr, mid + 1, right); // 递归排右半段 |
| 29 | Merge(arr, left, mid, right); // 左右两段各自排好后，合并起来 |
| 30 | } |
| 31 | |
| 32 | // 调用方式：MergeSort(arr, 0, n - 1); |
MergeSort 自己调用自己，把"排序整个区间"拆成"排序左半区间"和"排序右半区间"两个规模更小、结构完全相同的子问题——这正是递归的核心特征。递归到 left >= right（区间只剩 0 或 1 个元素）时停下来，因为 1 个元素不需要排序，直接就是有序的。| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n log n) | 归并排序不会因为数据"本来就有序"而变快 |
| 平均情况 | O(n log n) | 拆分固定是 log n 层，每层合并固定是 O(n) |
| 最坏情况 | O(n log n) | 三种情况复杂度完全相同，非常稳定 |
O(n) 的额外空间），不是"原地排序"。另外，归并排序在相等元素之间不会交换相对顺序（比较时写的是 arr[i] <= arr[j]，左边相等时优先取左边），这个性质叫"稳定排序"，在某些需要保持原始顺序的场景里很重要。这一节先重点吃透归并排序；同一模块的快速排序会在后面单独补上，两者都是"分治"思想的经典应用，但拆分和合并的方式正好相反。