归并排序

这是分治法理路分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。中“先解决小问题，再组合答案”的典型例子。两边已经有序，所以全体剩余项中的最小者必在两个首项之一；不必重新搜索整段，也不必撤回已经输出的项。

把合并展开成层，每个内部层总共处理 $O(n)$ 项，层数为 $O(\log n)$。这个图像解释时间界，但正确性还来自每次合并确实维护了次序和元素重数，两项缺一不可。

合并为什么正确且稳定 ​

排序 $[4,1,3,2]$ 时，两段递归结果为 $[1,4]$ 与 $[2,3]$。比较首项依次输出 $1,2,3$，再接上 $4$。合并的循环不变式理路循环不变式Loop invariant在循环初始化后成立，并在每次循环迭代后继续成立的断言。是：输出前缀已经有序，且每个已输出键不大于两侧任一剩余键；已输出与未输出记录合在一起，仍是原两段的全部记录及其重数。

每次选择较小首项保持这三点。循环结束后，两侧已全部输出，于是结果有序且没有丢失重复记录。递归按更小长度终止，结合基例便证明整体排序正确。

若相等键附带身份，例如输入 $[2_a,1,2_b,0]$，左、右半中的两个 $2$ 分别保留身份。最后合并在平局时先取 $2_a$，保住它早于 $2_b$ 的原次序。各半内部由递归保持稳定，跨半的平局由左优先保持稳定；若平局改取右侧，稳定性就可能失败。

表示和变体改变成本 ​

链表可以通过重接节点合并，不需要线性大小的辅助元素数组；普通递归版本仍需调用栈。自底向上的链表归并可以进一步避免递归栈，但那是另一份执行方案，不能只从“用了链表”推出全部额外空间为常数。

标准数组版本需要线性辅助空间。更复杂的原地归并算法确实存在，不能反过来把它们的空间界安到本页方案上。自然归并排序会利用已经有序的连续段，某些输入因此更快；本页递推描述的是固定近半分割、逐层合并的版本。

Powersort理路Powersort自然归并排序Powersort · Power sort · Powersort自然归并用相邻自然段中点的二进制分歧决定归并次序，构造保持叶序的近最优归并树，并分别核算比较、搬移和调度成本。先保留非降段与反转后的严格下降段，再按相邻原段中点的二进制分歧选择归并次序。对于段长比例pᵢ，归并体积距离最优有序树小于2n；该体积由记录参与归并的次数决定。galloping归并理路短段驱动的galloping归并Galloping merge · Exponential-search merge · 跳跃归并 · 短段驱动归并以较短有序段为驱动，用指数探测和二分批量越过长段前缀，证明稳定边界及按跳跃长度计费的比较界。则改变一次双路归并内部的比较方式，用指数探测批量越过长前缀，两项改动分别影响调度与比较。

最坏 $O(n\log n)$ 的比较数达到一般比较排序下界理路比较排序下界Comparison sorting lower bound任何最坏情形比较排序都需 Ω(n log n) 次比较。的渐近量级。稳定性则是另一项保证，由相等键的合并规则给出，不能从时间最优性推出。

归并适合顺序扫描。外存排序理路外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。在内存中缓冲多段并作多路归并，用更少轮次控制块传输；Funnel Sort理路Funnel Sortfunnel sort · 漏斗排序以递归多路合并器和分级缓冲，在不知道缓存参数时达到外存排序量级的块传输界。再用递归缓冲结构取得缓存无关界。它们与本页共享合并思想，但需分别给出内存容量、块大小和 I/O 成本。

归并过程也能计数逆序对：当右首项严格小于左首项时，它还小于左段全部剩余项，因而一次加入左段剩余项数。相等时先取左边，避免把相等键误计为逆序。并行实现理路并行算法模型parallel algorithm model · parallel computation model用总工作、关键路径、处理器数和通信成本共同描述并行算法，而不只报告理想加速比。则还要选择并行合并方法，不能只把两个递归调用同时启动，就宣称所有合并成本也被平分。