先聊点实在的。很多人学排序算法的时候最容易轻视的就是归并排序Merge sort它没有快速排序那种“平均性能神话”般的热度也没有冒泡排序、选择排序那么“好讲”。但你要是去问一个真正处理过海量数据排序、做过数据库内核或中间件的人他多半会告诉你——归并排序才是那个在危急关头真正扛事的算法。归并排序的核心思想就一句话把两个已经有序的序列合并成一个更大的有序序列再借助分治策略把整个排序问题拆成无数个“两两合并”的小问题。它不像快速排序那样依赖基准值选得好不好它的最坏时间复杂度、平均时间复杂度、最好时间复杂度统统都是 O(n log n)而且它还是几个主流排序里非常少见的稳定排序。这篇文章我想从思想原理、两种代码实现、手推示例、优化技巧到它在外部排序、链表排序等真实场景里的应用完整地讲一遍。同时会把我自己写归并排序时踩过的坑和实测有效的优化手段一并交代清楚希望能给准备面试的、写基础库的、或者单纯想把排序吃透的朋友一些帮助。1. 先把归并排序的核心思想拆明白1.1 分治不是玄学根基是两个有序序列的合并归并排序的起点其实特别朴素假设你手里有两堆已经排好序的扑克牌怎么把它们合成一堆有序的牌你只需要每次都看两堆牌最顶上那一张谁小就拿谁拿完再比较下一张直到某一边空了把另一边剩下的直接接上去。这个过程就是“合并merge”时间复杂度是 O(n)因为每个元素最多被比较一次、移动一次。问题来了待排序的数组一开始并不是两堆有序的牌怎么办这就用到分治。把数组从中间一分为二左边递归排好右边递归排好此时整个数组就变成了“左半有序 右半有序”可以合并了。那左半怎么排好继续一分为二直到每个子区间只剩一个元素——一个元素天然就是有序的。所以归并排序的本质就是先拆分到最小然后用“合并有序序列”这个基本操作一层层把数组拼回来。这个思路和“把大任务拆成小任务小任务解决后再汇总”的管理学逻辑一模一样也是分治算法思想最标准的入门案例。1.2 时间复杂度到底怎么算出来的很多初学者会背结论归并排序是 O(n log n)。但真要问到“这个 log n 从哪来”就卡住了。我习惯用递推的方式讲。设 T(n) 表示对 n 个元素排序的时间。每次递归我们把数组分成规模约 n/2 的两个子问题所以解决两个子问题的时间是 2T(n/2)再加上合并两个子数组的时间 O(n)。于是有T(n) 2T(n/2) O(n)把这一层一层展开第一层是 n第二层是 2 个 n/2加起来是 n第三层是 4 个 n/4加起来还是 n。因为每次规模减半所以一共有 log2(n) 层每一层处理的总数据量都是 n。总时间是 n × log2(n)也就是 O(n log n)。关键是这个复杂度没有任何“运气成分”。快速排序平均也是 O(n log n)但最坏会退化到 O(n^2)归并排序不管输入是什么样都是稳定地 O(n log n)。付出的代价就是额外内存空间下面细说。1.3 稳定排序和 O(n) 辅助空间意味着什么归并排序是稳定的这点很容易被人忽略但实际价值很高。“稳定”的意思是如果两个元素的排序键相等排序后它们的相对顺序不会改变。归并排序为什么稳定因为在合并两个有序序列时当左边元素和右边元素相等我选择先取左边那个这样等于值的左半部分元素始终排在右半部分元素前面相对顺序被原样保留。这种稳定性在真实业务里很有用。比如表格里先按时间排序再按用户 ID 排序如果第二次排序是稳定的那么同一个用户的多条记录内部仍然保持时间顺序如果用了不稳定的快速排序这个顺序就被打乱了。数据库索引、分页排序这些场景都非常看重这一点。至于空间复杂度归并排序需要一个和原数组等长的辅助数组来暂存合并结果所以额外空间是 O(n)。这是它对比快速排序最吃亏的地方快速排序是原地排序额外空间 O(log n)归并排序做不了严格意义上的原地合并除非用一些复杂度极高的技巧否则时间复杂度会退化。所以选择归并排序等于用空间换来了“稳定 最坏情况也可控”这两个重要性质。2. 代码实现从递归到迭代2.1 自顶向下递归版最直观也最容易写对递归版归并排序是最常见的写法也是面试手写时最推荐优先写出来的版本。我一般先写一个递归主函数再写一个 merge 函数负责合并两个有序区间。先看完整代码// 合并 [left, mid] 和 [mid1, right] 两个有序区间 void merge(vectorint arr, vectorint temp, int left, int mid, int right) { int i left; // 左半区起始 int j mid 1; // 右半区起始 int k left; // 辅助数组的写入位置 while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } // 左半区还有剩余直接拷过去 while (i mid) temp[k] arr[i]; // 右半区还有剩余直接拷过去 while (j right) temp[k] arr[j]; // 把合并后的结果拷回原数组 for (i left; i right; i) arr[i] temp[i]; } // 归并排序主函数 void mergeSort(vectorint arr, vectorint temp, int left, int right) { if (left right) return; // 区间为空或只剩一个元素 int mid left (right - left) / 2; mergeSort(arr, temp, left, mid); // 排左半 mergeSort(arr, temp, mid 1, right); // 排右半 if (arr[mid] arr[mid 1]) return; // 已经有序跳过一次合并 merge(arr, temp, left, mid, right); // 合并两个有序区间 }注意一个细节mid 的计算我用left (right - left) / 2而不是(left right) / 2。虽然在这个场景里 left 和 right 可能溢出导致的问题在普通面试题里不容易触发但写成前者是一个更安全的好习惯尤其是数组很大的时候。外层调用时辅助数组temp只需要创建一次不需要在每层递归里都 new 一个新数组。这是我很早以前踩过的坑一开始习惯在 merge 函数内部临时开一个新数组数据量一上去内存申请和释放的开销非常明显。提前分配好一个同等大小的空数组递归过程中不同的区间复用这个数组的不同位置性能立刻提升一截。2.2 merge 函数为什么是归并排序的灵魂很多人写归并排序主函数递归写得飞快一到 merge 就犯错。merge 最核心的是三个循环第一个循环同时比较左右两个区间第二、第三个循环分别把剩余元素接上。这里有一个很容易忽略的细节合并时用小于等于还是小于。我在代码里写的是if (arr[i] arr[j])。这个细节直接决定稳定性。如果写成当左右两边的值相等时会先把右边的元素放到辅助数组里左边那个后放相等元素的相对顺序就反了排序就变得不稳定。虽然数组元素是纯整数时看不出区别但如果是对象、是带有原始顺序的业务数据这个差异就是致命的。另外我发现很多人在 merge 里只关注前两个 while忘了最后把合并结果拷回原数组temp的内容覆盖到arr。如果省略这一步当前这一层递归返回后原数组对应区间还是旧数据合并结果就白白丢了。所以我在写 merge 函数时总是把“拷贝回原数组”这一步单独放在最后注释标清楚防止漏掉。如果你想让边界处理更简洁还可以用“哨兵”技巧在两个辅助数组的末尾放一个极大值比如INT_MAX这样两个 while 循环可以合并成一个 for 循环因为哨兵永远不可能被取出来当最小值。但我不太推荐在生产代码里用INT_MAX——如果数据里真的存在INT_MAX这个值哨兵就会参与比较程序当场出错。更稳妥的做法还是老老实实写三个 while。2.3 自底向上迭代版避免递归也能排序链表递归版虽然直观但递归调用本身有函数栈开销而且有些场景根本不适合递归比如待排序的是链表——链表没法像数组那样用下标快速二分。这时候可以用自底向上的迭代归并。思路是先把数组看成 n 个长度为 1 的有序区间然后两两合并得到长度为 2 的有序区间再两两合并得到长度为 4 的有序区间一直到整个数组有序。循环里用变量len表示当前每个区间的长度每轮过后len翻倍。参考实现void mergeSortIterative(vectorint arr) { int n arr.size(); vectorint temp(n); // len 是当前子区间的长度从 1 开始每轮翻倍 for (int len 1; len n; len 1) { // 每次合并两个长度为 len 的区间 for (int left 0; left n; left len 1) { int mid min(left len - 1, n - 1); int right min(left (len 1) - 1, n - 1); if (mid right) { merge(arr, temp, left, mid, right); } } } }这个版本和递归版本的本质完全相同只是把“先递归到最小再合并”的顺序变成了“先合并小段再逐步扩大”。它不需要递归栈也就不存在栈溢出风险。我实测过在数据量上千万、递归深度远达不到危险线的情况下两者时间差异不算大但迭代版胜在稳定可控而且链表版本非常自然。如果你要排序的是链表其实连temp数组都不需要——合并两个有序链表时只需要调整节点的 next 指针。用快慢指针找到链表的中点递归排序前后两半再调用一个mergeTwoLists合并即可。这也是 LeetCode 148 题的标准解法。3. 手把手推演一轮完整排序3.1 以数组 [38, 27, 43, 3, 9, 82, 10] 为例光看代码还是有点抽象我习惯用一个具体例子从头到尾推一遍。就拿教科书上最经典的数组[38, 27, 43, 3, 9, 82, 10]来说长度是 7递归拆分过程如下第 1 层mid 3拆成左半[38, 27, 43, 3]和右半[9, 82, 10]第 2 层左半再拆成[38, 27]和[43, 3]右半拆成[9, 82]和[10]第 3 层[38, 27]拆成[38]和[27][43, 3]拆成[43]和[3][9, 82]拆成[9]和[82]到这里每个区间都只剩一个元素天然有序开始合并[38]和[27]合并成[27, 38][43]和[3]合并成[3, 43][9]和[82]合并成[9, 82][10]保持[10]然后合并[27, 38]和[3, 43]先拿 3再拿 27再拿 38最后拿 43得到[3, 27, 38, 43]合并[9, 82]和[10]先拿 9再拿 10最后拿 82得到[9, 10, 82]最后合并[3, 27, 38, 43]和[9, 10, 82]依次取 3、9、10、27、38、43、82得到最终结果[3, 9, 10, 27, 38, 43, 82]你可以看到每一层要合并的数据总量都是 n7 个元素一共拆了约 log2(7) ≈ 3 层所以总的比较和移动次数接近 n log2(n)。注意“移动次数”其实大于比较次数因为归并不只是比较还要把每个元素搬运到辅助数组再搬回来。3.2 用代码验证输出观察排序过程如果你不满足于纸面推演我建议你直接在代码里加一行打印把每次 merge 前后的区间打出来。比如在 merge 入口处打印cout merge [ left , mid ] and [ mid1 , right ]。我当初学习时就是这么做的比看任何动画都直观。输出里你会清晰看到拆分 [0,3] - [0,1] 和 [2,3] merge [0,0] and [1,1] merge [0,1] 结果: [27,38,...] ...这种日志式的调试方法对排查递归类算法特别有效。如果你发现合并结果不对就往前推一步看两个子区间是否已经分别有序如果子区间本身无序那问题大概率出在更早的递归分支上而不是当前 merge。利用递归调用栈的层次可以快速缩小排查范围。3.3 比较器的秘密字符串、中文和 IP 地址排序很多人在实际项目中用归并排序会发现一个问题对字符串数组跑排序结果好像“不对”。其实算法本身没毛病问题通常出在比较方式上。归并排序的 merge 过程只认“小于等于”这种比较结果到底什么是“小”完全取决于你传入的比较函数。这个点非常重要。C 里如果直接用容器默认的operator对std::string排序比较规则是字典序按 ASCII/Unicode 码点逐个字符比较。对英文字符串“apple”“banana”“cherry”没问题但遇到中文默认的字典序是按 Unicode 编码在排不是按拼音或笔画。所以如果你想按拼音排序中文需要传入一个按拼音转换规则实现的比较器想按 IP 地址排序也绝不能直接用字符串比较因为192.168.1.100在字典序里会排在192.168.1.2前面正确做法是把 IP 转成 32 位整数再比较。归并排序的稳定性在这里也有实际价值如果你想实现“先按拼音排序再按笔画排序”稳定排序可以保证第二轮的排序不会破坏第一轮的结果这在处理中文姓名、中文地址等业务数据时非常实用。所以当你发现归并排序结果不符合预期先别急着怀疑算法检查比较器才是最合理的排查方向。4. 常见问题、优化技巧和避坑清单4.1 递归栈会爆吗什么时候需要换迭代版初学者经常担心递归太深导致栈溢出。归并排序的递归深度是 log2(n)不是 n。n 等于一百万时递归深度只有 20 层n 等于十亿时深度约 30 层。普通语言默认函数栈根本不会因为这几十层深度就爆掉。所以对数组排序来说“递归导致栈溢出”这个担心基本是多余的。真正需要警惕的是另一种情况数据源不是数组而是链表或者你所在的环境限制了调用栈大小比如某些嵌入式环境、部分脚本语言的递归限制。这时迭代版的优势就体现出来了。另外如果你用的是一个实现很糟糕的递归版本每层递归都新建一个临时数组那内存分配次数会达到 O(n log n)内存碎片和申请耗时都是灾难。所以优化优先级第一件事就是改成“外部只分配一次辅助数组”而不是急着把递归改成迭代。4.2 三个能明显提升性能的优化手段除了复用辅助数组还有三个优化我实测下来最立竿见影第一个是“已有序区间短路”。在递归函数的 merge 之前先判断if (arr[mid] arr[mid 1]) return;。如果左半最后一个元素已经小于等于右半第一个元素说明两个区间拼接后就是完全有序的不需要执行合并。对近乎有序的数据这个判断能省掉大量无效拷贝和比较。TimSort 也是沿着这个思路走得更远它会主动扫描出已经有序的片段run只对乱序部分排序。第二个是“小数组切换到插入排序”。当待排序区间长度小于某个阈值常见的是 16 左右插入排序的优势就体现出来了。原因在于插入排序没有递归调用、不需要额外空间、对缓存友好而且在小规模数据上常数极小。归并排序递归到很深层时全是长度为 1~8 的小区间继续递归和 merge 的固定开销远大于一次直接插入。这个混合策略在 Java 的Arrays.sort、Python 的TimSort里都能找到影子。第三个是“减少拷贝次数”。标准递归版里merge 之后要把辅助数组内容拷回原数组如果你的实现允许可以把“原数组”和“辅助数组”的角色在每层递归中互换也就是在递归的不同深度交替使用两个数组作为源和目标。这样虽然不能完全消灭拷贝但能降低一部分整体带宽消耗。不过这个优化对代码可读性打击很大面试时我不建议主动展示现实中真要优化还是优先考虑前两点。4.3 归并排序和快速排序我到底该选谁这里我做一个很直接的对比例表方便你以后做技术选型维度归并排序快速排序时间复杂度最坏/平均/最好都是 O(n log n)平均 O(n log n)最坏 O(n^2)空间复杂度O(n) 辅助数组O(log n) 递归栈稳定性稳定不稳定标准版缓存友好性较差要搬移大量数据较好原地分区链表适配性很好只需改指针较差需要随机访问典型应用外部排序、数据库、框架稳定排序通用库排序、语言内置 sort如果你只是给一个几百万元素的普通数组排序标准库的快速排序或者内省排序通常更快因为它对 CPU 缓存更友好。但如果你需要稳定排序、数据在磁盘上放不下、待排序对象是链表节点或者要求最坏情况下也不能掉链子归并排序就是更优解。很多语言标准库的做法也印证了这一点C 的std::sort默认用内省排序快速排序 堆排序 插入排序的混合但std::stable_sort通常基于归并排序。5. 归并排序如何在真实项目里扛事5.1 外部排序内存装不下时归并几乎是唯一选择假设你有 1 GB 的文本数据需要排序但内存只有 100 MB快排再快也排不了因为数据根本装不进内存。这时归并排序的“合并”思路就派上用场了。做法是先把 1 GB 文件切成 10 个 100 MB 的小文件分别读进内存排序后写回磁盘——这就是 10 个已经有序的小文件也就是 10 路有序序列。然后拿出一个大小等于文件数的堆或者败者树从 10 个文件里各读一条记录堆顶就是全局最小把它写进输出文件再从它来源的那个文件补一条记录进堆。这个过程就是典型的多路归并排序本质上是归并排序合并操作的外存版本。外部排序几乎是归并排序思想最纯粹的应用场景大数据离线计算框架 shuffle 阶段也大量使用类似机制。5.2 链表排序归并排序的天然主场数组可以用随机访问快速定位中点但也因此可以用快速排序原地交换。链表就尴尬了只能顺序访问没法按下标“微操”。这时候归并排序的优势就非常明显——归并排序最核心的操作就是合并两个有序链表只需要改改指针完全不需要额外数组。也就是说用递归或迭代归并对链表排序辅助空间可以从 O(n) 降到 O(1)只靠指针操作就能完成。LeetCode 148 题“排序链表”劝退过很多人但只要你掌握了归并排序这个题就是典型的送分题。5.3 藏在框架和数据库里的归并排序很多时候你觉得自己没主动用过归并排序但事实上它就在你手边。Java 的Arrays.sort在对引用类型排序时用的就是 TimSort——TimSort 的核心思想就是“识别有序片段 归并合并”。Python 的sorted和list.sort用的同样是 TimSort。你每次调用这些接口归并排序都已经在背后默默工作了。数据库里更明显。MySQL 在做大结果集排序时如果排序数据量超出了sort_buffer_size它会先把数据分块排序写入临时文件再对这些有序文件做归并合并。执行计划里如果出现Using filesort内部大概率就有归并逻辑。我在实际排查慢 SQL 时每次都先确认排序是否走了索引一旦确认走了 filesort就会评估临时文件数量和归并次数——归并轮数太多意味着磁盘 I/O 成倍增长这时候优化方向就是扩大排序缓冲区或者给查询加上合适的索引从源头上减少需要排序的数据量。关于归并排序最后再分享一个我自己的习惯。我平时写归并排序一定先写 merge 函数再写主排序函数。因为 merge 是纯逻辑函数输入输出非常明确单独调试起来非常快。等 merge 确认无误主函数递归几乎不会出错。还有一个小技巧实现时把辅助数组的临时区域长度稍微多开一点比如n 8不是为了业务需要而是防止某些边界计算失误时越界写坏内存尤其在你手写自底向上迭代版本的时候这个缓冲能帮你避免一些诡异的崩溃。排序算法看起来是个老掉牙的话题但每一次重新梳理我都能在细节里发现新的东西。