14.5.6 归并排序

归并排序也叫合并排序，最常见的是二路归并：把两个已有序的子表合并成一个更大的有序表。它体现了典型的分治思想：先把大问题拆小，再把小问题的结果合并回来。

二路归并在做什么

归并排序的前提动作是：两个子表已经各自有序。合并时用两个指针分别指向两个子表当前未处理的最小元素，每次把较小者复制到辅助数组中，对应指针后移。某一边用完后，另一边剩余元素直接复制。

以两个有序表为例：

R = [57, 68]
S = [52, 59]

比较	放入结果	指针变化	当前结果
57 与 52	52	S 指针后移	[52]
57 与 59	57	R 指针后移	[52,57]
68 与 59	59	S 指针后移，S 越界	[52,57,59]
R 剩余 68	直接复制	结束	[52,57,59,68]

课程里强调的“省时间”就在这里：当某一边已经耗尽，另一边不需要继续比较，直接复制即可。

完整归并排序过程

归并排序先不断拆分，直到子序列长度为 1。长度为 1 的序列天然有序；然后两两合并，得到长度为 2、4、8……的有序段。

flowchart TD
  A["57 68 52 59 72 28 96 33"] --> B["57 68 52 59"]
  A --> C["72 28 96 33"]
  B --> D["57 68"]
  B --> E["52 59"]
  C --> F["72 28"]
  C --> G["96 33"]
  D --> H["57 | 68"]
  E --> I["52 | 59"]
  F --> J["72 | 28"]
  G --> K["96 | 33"]

合并方向与拆分方向相反：

[57] [68] -> [57,68]
[52] [59] -> [52,59]
[57,68] [52,59] -> [52,57,59,68]

实际题目不一定保证元素个数是偶数。多出来的单个元素可以留到下一轮参与更大有序段的归并，不影响算法成立。

复杂度为什么是 $O(n\log n)$

归并排序有两层代价：

1. 拆分层数：每次二分，层数约为 ${\log }_{2}n$。
2. 每层合并：所有元素在这一层都会被复制/比较处理一遍，总量约为 $n$。

因此总体时间复杂度为：

$$T(n)=O(n{\log }_{2}n)$$

归并排序的一个重要优点是时间复杂度稳定：最好、平均、最坏都为 $O(n\log n)$。它不像快速排序那样会因为枢轴选择不好退化到 $O(n^2)$。

空间复杂度与稳定性

归并时需要一个临时数组存放合并结果，再复制回原数组。因此辅助空间通常为 $O(n)$。这也是它比堆排序更“吃空间”的地方。

它为什么稳定？合并两个有序表时，如果左右两边当前关键字相等，只要规定先取左边元素，就能保持原始相对顺序。整个合并过程不会发生隔空交换，所以稳定性可以层层保持。

算法	时间复杂度	辅助空间	稳定性	主要取舍
堆排序	$O(n\log n)$	$O(1)$	不稳定	省空间，但不稳定
快速排序	平均 $O(n\log n)$，最坏 $O(n^2)$	$O(\log n)$ 到 $O(n)$	不稳定	平均速度快，但受枢轴影响
归并排序	始终 $O(n\log n)$	$O(n)$	稳定	稳定可靠，但占用额外数组

课程里给出的记忆点很有用：常见 $O(n\log n)$ 排序中，若强调稳定，通常选归并；若强调空间优势，通常选堆排序；若强调内部排序平均运行时间，快速排序常被认为表现很好。

归并比较次数题怎么做

软件设计师题目可能给两个递增序列 $A$ 和 $B$，长度分别为 $m$ 和 $n$，且 $m<n$，问把二者归并成递增序列时哪种排列比较次数最少。

解题关键：归并过程中只有在两个表都还没越界时才比较；一旦某个表耗尽，另一个表剩余元素直接复制。

如果 $A$ 的所有元素都小于 $B$ 的所有元素，那么只需依次比较 $A_1,\dots ,A_m$ 与 $B_1$，共 $m$ 次，之后 $B$ 剩余元素直接复制。这比交错排列的比较次数更少。

考试判断

• “二路归并”“合并两个有序表”是归并排序信号。
• “稳定且 $O(n\log n)$”优先归并。
• “需要 $O(n)$ 辅助空间”常指归并。
• “最坏情况下时间复杂度最低”若选项有插入、冒泡、快速、归并，通常选归并，因为快速最坏为 $O(n^2)$。

单选

对 $n$ 个记录排序，若只考虑最坏情况下的时间复杂度，下列算法中通常最低的是哪一个？

A简单选择排序B快速排序C归并排序D希尔排序

本节小结

归并排序靠“分而治之 + 有序合并”获得稳定的 $O(n\log n)$ 时间复杂度。它牺牲 $O(n)$ 辅助空间，换来稳定性和最坏情况可靠性，是排序算法对比题里的高频选项。