归并排序

归并排序把难以整体处理的“排序”分解为两个独立的半区排序和一次稳定线性合并。合并阶段只比较两个有序列表各自尚未取出的最小元素，较小者一旦输出便不可能被另一侧尚未出现的元素越过；这个局部不变式使合并无需回溯，每个元素每层只被处理常数次。每层总合并量为 $n$，层数约 $\log n$，因此最坏时间稳定在 $\mathrm{\Theta }(n\log n)$。

排序 [4,1,3,2]，先得 [1,4] 与 [2,3]，再线性合并为 [1,2,3,4]。自然归并排序可利用输入中已有的有序段。归并排序不必原地；声称标准数组版本只需 $O(1)$ 额外空间是错误的，虽然存在更复杂的原地归并算法。它的 $\mathrm{\Theta }(n\log n)$ 比较数达到一般比较排序下界的渐近最优阶。

常见数组实现需要 $O(n)$ 辅助空间；链表上可通过指针重连低成本合并。原地归并存在更复杂算法，不能把“分治”自动等同于 $O(\log n)$ 额外空间。对极小子数组切换插入排序常改善常数，但不改变渐近界。

比较排序公理库比较排序Comparison sorting仅通过元素两两比较确定排列次序的排序模型。提供模型，分治法公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。提供结构，递归式公理库递推关系Recurrence relation用先前项规定序列当前项的关系。给出成本。归并的顺序访问适合外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。：内存同时缓冲多段并作多路合并，可减少块传输轮数。它也用于稳定排序、逆序对计数与并行流合并。

主存 merge sort 的 $O(n\log n)$ 比较并未描述数据移动层次。外存排序公理库外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。一次并 $M/B$ 路，把成本写成 Sort$(N)$ I/O；Funnel Sort公理库Funnel Sortfunnel sort · 漏斗排序以递归多路合并器和分级缓冲，在不知道缓存参数时达到外存排序量级的块传输界。以递归漏斗获得缓存无关排序界；Buffer Tree公理库Buffer Treebuffer tree · 缓冲树在高扇出树节点积累操作并批量下推，以排序量级 I/O 支持批量动态操作。把批量归并思想用于动态外存更新。并行模型公理库并行算法模型parallel algorithm model · parallel computation model用总工作、关键路径、处理器数和通信成本共同描述并行算法，而不只报告理想加速比。还要分别报告 work 与 depth。相同“归并”机制在四种模型中的成本坐标不同。