八大排序系列（四）：归并排序 —— 分治思想的另一条路径，稳定排序的代表

八大排序系列四归并排序 —— 分治思想的另一条路径稳定排序的代表上一篇我们拆解了快速排序 —— 这个靠「分区 递归」把排序效率拉到 O (nlogn) 的工业级算法结尾留下了一个核心问题同样是分治思想归并排序走的「先递归、再合并」路线和快排到底有什么本质不同今天这篇我们就彻底讲透归并排序同时把这个问题说清楚。昨日疑问收尾两种分治路径的本质差异学完归并再回头看两条分治路径的差异其实非常清晰它们对「分治」的发力点完全不同。快排的核心在分区排序工作发生在递归之前。每选好基准、完成一次分区基准元素就已经落到了它的最终位置左右子区间也已经满足「左小右大」的宏观有序。后续递归只是把同样的逻辑下沉到子区间不需要额外的合并步骤 —— 子区间各自排完整个数组自然就有序了。归并排序的核心在合并排序工作发生在递归之后。它的拆分阶段极其简单就是无脑从中间二分不做任何排序操作一直拆到每个子区间只剩一个元素天然有序。真正的排序逻辑全在回溯时的「合并两个有序数组」里完成。所有的性能、所有的特性也都围绕合并操作展开。一个先排序再递归一个先递归再排序一个重分区一个重合并。这就是两种分治思路最本质的分野。归并排序的核心思想先拆到底再逐层合并归并排序的整体流程非常规整可以拆成标准的三步拆分数组以中点为界把当前区间切成左右两半递归拆分直到子区间长度为 1递归排序子区间对左右两个子区间分别执行归并排序合并有序数组用双指针法把两个有序的子区间按大小顺序合并到临时数组再覆盖回原数组的对应位置其中合并操作是整个算法的灵魂用两个指针分别指向左右子数组的起点每次取两个指针中更小的元素放入临时数组对应指针后移直到某一边的元素全部取完再把另一边剩余的元素直接追加到末尾。整个过程只需要一次线性遍历就能完成两个有序数组的合并。也正因为拆分只是纯粹的二分不需要选基准、不需要考虑分区均匀度归并排序的性能几乎不受原始数据分布的影响表现极其稳定。两种实现方式递归与迭代归并排序主要有两种主流实现思路不同但都绕不开 O (n) 的辅助数组开销。1. 自顶向下递归版这是最符合直觉、最容易理解的写法从整个数组开始不断二分递归拆到底层再逐层向上合并。写递归版最容易踩坑的是中点计算与区间边界。比如中点是用left (right - left) / 2还是(left right) / 2区间是左闭右闭还是左闭右开差一个下标就可能导致排序错误或死递归。我当时调试的方法很朴素但有效拿一个长度很小的数组手推每一层递归的左右边界对照代码一步步走很快就能定位问题。2. 自底向上迭代版这种写法完全去掉了递归直接从最底层开始初始时每个元素自身就是一个长度为 1 的有序区间然后两两合并成长度为 2 的区间再合并成长度为 4 的区间以此类推直到合并完整个数组。和递归版相比它的核心优势是消除了递归栈的开销既省去了函数调用的 CPU 成本也避免了递归深度过大导致栈溢出的风险内存压力更小运行速度也更快。但要注意的是它依然需要一个同等大小的辅助数组来做合并O (n) 的空间开销并没有消失。特性分析稳定的复杂度与天然的稳定性时间复杂度真正稳定的 O (nlogn)归并排序是少有的、最好 / 最坏 / 平均时间复杂度全都是 O (nlogn) 的排序算法。原因很直观拆分是固定的二分递归层数永远是 logn不会因为数据有序、逆序就发生变化每一层递归中所有子数组合并的总元素量都是 n。无论原始数据是完全有序、完全逆序还是随机乱序执行的总操作数都基本一致性能波动极小。这种极强的稳定性是快排做不到的。排序稳定性天然稳定的经典代表归并排序是天然的稳定排序它的稳定性完全由合并逻辑保证当左右两个子数组出现值相等的元素时优先取用左边数组的元素相等元素的原始先后顺序就会被完整保留。稳定性在业务场景里的价值非常实际。比如我们有一张订单列表已经按下单时间排好了序现在需要再按金额排序要求金额相同的订单依然保持原本的时间顺序 —— 这种场景就必须用稳定排序才能实现。很多人觉得稳定性没用只是因为还没遇到多字段排序的需求而已。空间复杂度无法回避的 O (n)空间开销是归并排序最明显的短板。递归版需要 O (n) 的辅助数组 O (logn) 的递归栈空间整体空间复杂度 O (n)迭代版省去了 O (logn) 的栈空间但核心的 O (n) 辅助数组依然存在这也是它在内存排序场景中始终竞争不过快排的核心原因。算法定位内存排序的备选外排序的王者归并排序优点很突出性能稳定、排序稳定、最坏情况依然高效。但在普通的内存排序场景里它很少成为首选。核心原因就是 O (n) 的额外空间代价太高 —— 当数据量达到 GB 级额外开辟一倍内存的成本远大于性能稳定带来的收益。而快排近乎原地的空间开销、更优的缓存局部性综合性价比要高得多。但在外排序场景下归并排序的思想就是绝对的主流。 所谓外排序就是数据量太大比如几十 GB 甚至 TB 级的日志、文件内存完全装不下必须借助磁盘分批处理的排序场景。归并的思路天然适配这种场景先把大文件拆成一个个能放进内存的小分片逐个读入内存排好序再写回磁盘最后用多路归并的方式把这些有序小文件一层层合并成最终的有序大文件。整个过程不需要全量数据进内存靠归并思想就能完成超大规模数据的排序这也是大数据处理中最经典的思路之一。学习复盘与感悟手写归并排序的过程里我卡最久的就是区间边界和中点计算差一个下标结果就完全不对最后还是靠手推小数组、逐行调试才彻底理顺。学完快排和归并这两种分治排序最大的感受是分治从来不是一个固定的公式而是一种「拆解大问题、逐个解决、再合并结果」的思维方式。同样的思想发力点不同就能演化出特性完全不同的算法各自适配不同的场景。当然目前对分治的理解还不算完整等学完堆排序 —— 这个靠数据结构优化实现的 O (nlogn) 排序再回头整体复盘应该会有更系统的认知。下一篇我们就来聊堆排序看看完全二叉树这种数据结构是怎么把朴素的选择排序直接优化到 O (nlogn) 量级的。