归并排序
归并排序（Merge Sort）是分治思想最经典的体现——把数组对半切成两段，各自排好序，再用一次 O(n) 的 merge 操作把两个有序段「缝」成一个有序整体。这个「分两半各自排、再合并」的递归结构天然构成一棵高度 log₂ n 的递归树，每层合并工作量为 n，于是最好、平均、最坏都是 O(n log n)——这是它相对快排最大的优势：没有最坏情况退化。同时 merge 时「左半取小」的合并规则天然保证稳定性（相等元素的相对次序不变），使它成为对稳定性敏感场景（数据库、多关键字排序）的首选内排序之一。
归并排序的全部考点都源于一个结构事实：分治递归 + O(n) merge ⇒ O(n log n) 稳定。由此衍生出三大主题：①两种实现写法——自顶向下递归（先分后合，最直观）与自底向上迭代（从 1 元素两两 merge 到 n，无递归开销）；②merge 操作本身——双指针比较放小，是「分离指针」的典型应用，也是逆序对计数的天然载体；③归并思想的外延——外排序（海量数据分块排序后多路归并，Tape 排序）、Timsort（归并 + 插入，Python/Java 实际使用的排序）、链表归并排序（O(1) 额外空间排序链表）。其代价是O(n) 辅助空间（merge 要一个临时数组），这让它在「原地排序」赛道上不如快排/堆排。
评价
优点
- O(n log n) 稳定一致：最好、平均、最坏全是 O(n log n)，不像快排会退化到 O(n²)——对最坏延迟敏感的场景（实时系统、对抗性输入）首选归并。
- 稳定排序：merge 时「左半 ≤ 右半则先取左半」保证相等元素相对次序不变，这是快排/堆排做不到的——数据库、多关键字排序（先按 A 排再按 B 排）依赖稳定性。
- 适合外排序：merge 是顺序访问（两路各自从头扫到尾），对磁盘/磁带等顺序存储设备极友好，是海量数据外排序的标准算法。
- 适合链表排序：链表归并可做到 O(1) 额外空间（改指针而非搬数组），是链表排序的最优解之一。
- 并行友好：左右两半的递归排序彼此独立，可天然并行执行。
缺点
- O(n) 辅助空间：merge 需要一个长度为 n 的临时数组，这不是「原地」算法——对比快排 O(log n) 栈空间、堆排 O(1)，归并在空间上是三者最差的。
- 常数因子较大：递归调用 + 数组拷贝的开销，使归并的实际速度通常慢于 randomized 快排（虽然大 O 相同）——这是多数库默认用快排而非归并的原因。
- 不是原地：无法像快排那样在原数组上靠 swap 完成，对内存受限环境不友好。
本叶地图
- 入门 —— 分治思想、O(n log n) 三态一致、稳定性、O(n) 辅助空间、与快排怎么选
- 分治与合并 —— 自顶向下递归、自底向上迭代、merge 操作双指针详解、两种代码实现与复杂度分析
- 应用：逆序对、外排序与 Timsort —— 逆序对计数、海量数据外排序（多路归并）、Timsort、链表归并排序、为何数据库爱用归并
- 参考 —— 复杂度表、递归/迭代/merge/逆序对代码模板、与各排序对比、易错点