企业官网建设流程全解析

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

上一篇我们拆解了快速排序 —— 这个靠「分区 + 递归」把排序效率拉到 O (nlogn) 的工业级算法，结尾留下了一个核心问题：同样是分治思想，归并排序走的「先递归、再合并」路线，和快排到底有什么本质不同？今天这篇我们就彻底讲透归并排序，同时把这个问题说清楚。

昨日疑问收尾：两种分治路径的本质差异

学完归并再回头看，两条分治路径的差异其实非常清晰：它们对「分治」的发力点完全不同。

快排的核心在分区，排序工作发生在递归之前。每选好基准、完成一次分区，基准元素就已经落到了它的最终位置，左右子区间也已经满足「左小右大」的宏观有序。后续递归只是把同样的逻辑下沉到子区间，不需要额外的合并步骤 —— 子区间各自排完，整个数组自然就有序了。

归并排序的核心在合并，排序工作发生在递归之后。它的拆分阶段极其简单，就是无脑从中间二分，不做任何排序操作，一直拆到每个子区间只剩一个元素（天然有序）。真正的排序逻辑，全在回溯时的「合并两个有序数组」里完成。所有的性能、所有的特性，也都围绕合并操作展开。

一个先排序再递归，一个先递归再排序；一个重分区，一个重合并。这就是两种分治思路最本质的分野。

归并排序的核心思想：先拆到底，再逐层合并

归并排序的整体流程非常规整，可以拆成标准的三步：

1. 拆分数组：以中点为界，把当前区间切成左右两半，递归拆分，直到子区间长度为 1
2. 递归排序子区间：对左右两个子区间分别执行归并排序
3. 合并有序数组：用双指针法，把两个有序的子区间按大小顺序合并到临时数组，再覆盖回原数组的对应位置

其中合并操作是整个算法的灵魂：用两个指针分别指向左右子数组的起点，每次取两个指针中更小的元素放入临时数组，对应指针后移；直到某一边的元素全部取完，再把另一边剩余的元素直接追加到末尾。整个过程只需要一次线性遍历，就能完成两个有序数组的合并。

也正因为拆分只是纯粹的二分，不需要选基准、不需要考虑分区均匀度，归并排序的性能几乎不受原始数据分布的影响，表现极其稳定。

两种实现方式：递归与迭代

归并排序主要有两种主流实现，思路不同，但都绕不开 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) 量级的。