归并排序Merge Sort大概是那种“上课听懂了、看代码也懂了但自己动手一写就卡壳”的经典算法。网上讲它的文章很多但大部分要么只贴一份代码然后甩出O(nlogn)结论要么把递归树画得无比复杂。这篇我想换个讲法先解决“为什么归并排序不可替代”的问题再把合并操作、递归展开、时间复杂度推导演示一遍最后聊几个我在实际工程里踩过、也看别人踩过的坑。内容会尽量保持可以跟着动手复现的程度无论你是刚学到排序的初学者还是想彻底弄懂复杂度来源的备考党应该都能有收获。1. 为什么归并排序值得专门开一篇来写1.1 其他O(nlogn)排序做不到的一件事稳定很多人第一次接触归并排序时第一个疑问都是快排平均复杂度也是O(nlogn)堆排最坏情况也是O(nlogn)为什么还要专门学归并答案的第一层是稳定性。所谓稳定排序指的是如果两个元素的值相等排序后它们的相对顺序不会改变。快排和堆排在元素交换的过程中很容易把相等元素的先后顺序打乱而归并排序天然就是稳定的。这个特性平时感觉不到但一旦数据带“主键次键”就非常关键。举个例子。假设你有一份学生名单先按班级排好序然后希望在外层再按成绩排序成绩相同的同学之间希望保持“班级号较小在前”的原有顺序。这种场景下稳定排序能直接保证二次排序后班级内部仍然有序。包括我接触过的不少业务系统在按时间排序后再按优先级排序的场景里都会刻意选择稳定排序实现。所以归并排序不是“快排的备胎”它在需要稳定性的场景里是首选。而这也是很多标准库的排序实现中会针对对象数组使用归并排序变体的根本原因。1.2 可预测的性能与外部排序场景第二个不可替代的点是它没有明显的最坏情况。快速排序最坏情况下会退化到O(n^2)虽然通过随机化选枢轴可以极大降低概率但理论上它依然存在性能毛刺。归并排序无论数据原本是正序、逆序还是完全随机都严格跑在O(nlogn)时间复杂度曲线非常稳定。这在大规模数据处理、对时延要求严格的服务端排序任务里是很重要的确定性优势。第三个优势是外部排序。当数据量大到无法全部加载进内存只能一部分一部分地读写磁盘时快排的原地交换策略会失效——因为没法把整个数据放进内存随机访问。而归并排序天然适合分块处理把大文件切分到内存可容纳的块块内排序后落盘再用多路归并的方式把有序块逐步合并成大文件。可以说几乎所有数据库和分布式系统里的外部排序方案底层核心都是归并思路。这个应用价值很容易被只刷算法题的人忽视。1.3 归并的递归思路归并排序的思路用一句话概括把一个数组从中间切开分别排序再把两个有序半段合并成一个有序数组。切开之后的两个半段递归地重复同样操作直到每段只剩一个元素。单个元素天然有序这时再一级一级合并回去整个数组就有序了。这个思路属于典型的“分治”思想。理解它不困难困难的是把“合并”这个过程写对——也就是下一节要拆解的内容。很多人递归分到一半就不知道怎么处理两个有序数组的合并了其实合并算法本身完全独立于递归先把它吃透归并排序就拿下大半。2. 归并排序的心脏合并两个有序序列2.1 merge的机械过程合并操作的目标非常明确给定两个已经各自有序的数组或同一个数组的两个区段输出一个合并后仍然有序的结果数组。做法也特别朴素同时从两个序列的开头往后扫描每次比较当前位置的两个元素把较小的那个放入结果集然后对应的指针向后移动一步如果某一个序列先被取空了就把另一个序列剩余的部分直接倒进结果集。这个过程的比较次数有很强的规律。两个长度分别为m和n的有序序列最坏情况下需要比较mn-1次最好情况下比如一个序列的所有元素都小于另一个序列的首元素只需要比较min(m, n)次。但是无论怎么算合并的总代价都在O(mn)也就是和两个序列的总长度成正比。2.2 经典merge代码与实现细节下面用类Python风格的伪代码展示一遍核心过程。实战中我倾向于把merge写成独立的函数这样递归部分可以保持干净。def merge(arr, left, mid, right): # left..mid 是左半段mid1..right 是右半段两段各自有序 temp [] i, j left, mid 1 # 两个指针同时向右扫描 while i mid and j right: if arr[i] arr[j]: temp.append(arr[i]) i 1 else: temp.append(arr[j]) j 1 # 左半段还有剩余 while i mid: temp.append(arr[i]) i 1 # 右半段还有剩余 while j right: temp.append(arr[j]) j 1 # 写回原数组 for idx, val in enumerate(temp): arr[left idx] val这里有一个值得抠的细节为什么比较条件用而不是如果左半段的元素等于右半段的元素用会先把左半段的元素放进结果集这意味着相等元素的原始先后顺序被保留了下来。如果这里误写成相等元素会先取右半段的稳定性就被破坏了。这个细节在工程代码里非常关键也是很多人在手写归并排序时稳定性丢失的真正原因。提示如果你在某个场景下明确要求“相等元素的顺序必须和原数组保持一致”那么归并排序合并时务必使用比较。2.3 一个常见的边界坑临时数组的索引上面代码里写回原数组的循环用的是arr[left idx] val。有些初学者会把这里写成arr[idx] val这在小数组测试时可能碰巧没问题因为left恰好为0但只要递归深入到left不为0的区间立刻会把数据写回错误位置。我自己的习惯是在一开始就明确三个区段的语义区段下界上界长度左半段leftmidmid - left 1右半段mid 1rightright - mid合并结果0right - leftright - left 1每次写回时都要记得把临时数组的下标偏移到left这个偏移处理好了归并排序基本就成功了一半。3. 递归展开把数组拆到不能再拆再合回去3.1 递归的边界条件归并排序的递归部分其实很短核心就是三步计算中点、递归左半段、递归右半段、合并左右。def merge_sort(arr, left, right): if left right: return mid (left right) // 2 merge_sort(arr, left, mid) merge_sort(arr, mid 1, right) merge(arr, left, mid, right)递归出口是left right也就是当前区间内没有元素或只有一个元素。为什么在这里停因为“一个元素”天然是有序的不需要再分了。很多人写递归总是纠结“什么时候递归结束”这里的逻辑其实非常直接区间长度小于等于1就返回。这个边界用的区间表示法是闭区间也就是left和right都包含在待排序范围内。闭区间和半开区间很容易弄混我建议在一开始确定一种写法后就保持一致不要来回切换否则mid的计算和边界判断很容易出错。3.2 亲手把 [6, 1, 8, 4, 3, 9] 走一遍为了直观感受递归过程我们拿一个只有6个元素的数组完整拆解一遍。初始状态[6, 1, 8, 4, 3, 9]区间为整个数组。第一步mid 2分成左半段[6, 1, 8]和右半段[4, 3, 9]。左半段继续分mid 1分成[6]和[1, 8]。[6]长度为1直接返回。[1, 8]继续分mid 2分成[1]和[8]这两个都长度为1合并得到[1, 8]。这一步把左半段从[1, 8]和[6]合并成[1, 6, 8]。右半段[4, 3, 9]同样处理mid 4分成[4]和[3, 9]。[3, 9]继续分成[3]和[9]合并得到[3, 9]再将[4]与[3, 9]合并得到[3, 4, 9]。最后把[1, 6, 8]与[3, 4, 9]合并过程如下比较1和31进结果比较6和33进结果比较6和44进结果比较6和96进结果比较8和98进结果9直接落入结果。最终得到[1, 3, 4, 6, 8, 9]。这个手动展开的过程我建议每个人都做一遍。不用复杂的数组就6到10个数字在纸上画出每一层的合并结果。你会发现归并排序和快排的最大区别它没有任何“某一步做了关键决定”的感觉每一步都是机械的切半、合并最终结果却完全正确。这种“无巧思但必然正确”的算法反而是大多数工程场景最愿意用的。3.3 递归深度与栈空间长度为n的数组每次切半递归深度是O(logn)。这个深度相当浅100万个元素只需要大约20层递归。所以归并排序的递归在深度上并不危险。但要注意这与它额外的O(n)空间是两个完全不同的概念。递归深度消耗的是调用栈空间是O(logn)级别而合并时创建的临时数组才是主要内存开销是O(n)级别。这两个点经常被人混淆面试里也常被问。你只需要记住归并排序的空间复杂度是O(n)而不是O(logn)这O(n)来自合并过程的临时存储。4. 时间复杂度分析O(nlogn)是怎么算出来的4.1 递推公式分析归并排序时间复杂度时假设输入规模为n写出它的递推关系。对一个数组归并排序可以先排左半段再排右半段然后合并。整个流程对应的时间关系是T(n) 2 * T(n/2) O(n)其中2 * T(n/2)代表两个规模为n/2的子问题耗时O(n)代表合并两个有序半段的耗时。边界条件是T(1) O(1)。这个递推式是整个复杂度分析的起点。它能推出O(nlogn)问题在于怎么直观理解这个结果。4.2 递归树展开的直观解释把递推式画成一棵递归树每一层看成一个独立的合并开销。第一层只处理一个规模为n的数组合并开销是n第二层有两段规模为n/2的数组需要合并每一段合并耗时n/2两层合计开销n第三层有四段规模为n/4的数组需要合并每段合并耗时n/4合计开销n依次类推。每一层的总合并开销都是n。整棵树一共有多少层因为每次规模减半从n降到1需要logn次所以总开销是n × logn O(nlogn)这里的关键洞察在于分治方法不像暴力枚举那样把问题拆成各个独立部分分别处理它把合并代价均匀地分摊到了每一层而层数是logn级别的。这和快速排序的空间划分思想形成鲜明对比快排每层划分并不产生额外的合并代价依赖的是“选好枢轴后元素直接落位”一旦枢轴选得不好划分就不均匀复杂度就会退化。4.3 为什么最坏情况也是O(nlogn)快速排序最坏情况是O(n^2)归并排序却没有这个问题。原因在于归并排序的时间消耗根本不由“数据原本长什么样”决定。不管数据是否有序归并排序都会先机械地切成两半再机械地合并两半。合并时虽然比较次数有一定浮动但这个浮动范围始终被O(mn)约束住。逆序度极高的数据不会让某次划分变成1和n-1这样的极不均衡结构——因为归并的切分只看数组下标根本不看元素值。所以归并排序的时间复杂度是一个严格的、与输入分布无关的O(nlogn)上界。这也是为什么在某些对时延抖动极其敏感的业务系统中宁可接受更大的内存开销也要使用归并排序变体。4.4 空间复杂度O(n)如何理解归并排序需要与输入规模成正比的额外空间本质原因是合并两个有序序列时必须先在一个独立空间里排好再覆盖回原数组。无法做到像快排那样在数组内部直接交换元素完成全部操作。一个常见误区是“每次合并都申请临时数组空间应该是O(logn)层数乘以每层大小”。但算法分析里计算空间复杂度看的是同一时刻需要的最大额外空间而不是整个运行过程累计创建的空间总量。递归到最深层时调用栈上只需要为当前层级合并准备一个总长度为n的临时数组更上层的临时数组可以复用或已释放。因此额外空间是O(n)而不是O(nlogn)。注意不同语言实现的细节不同但理论上的空间复杂度不会低于O(n)。这是归并排序相比快排和堆排最大的代价。4.5 与其他排序的横向对比排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定快速排序O(nlogn)O(n^2)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定从这个表可以很清楚地看到归并排序的定位如果不关心稳定性且内存非常紧张堆排或快排往往更合适如果数据规模大、要求稳定、最坏情况也不能有性能毛刺归并就是更稳妥的选择。5. 拿数据说话实测里归并的拐点在哪5.1 测试是怎么设计的学了理论我还想确认一件事在实际跑起来时归并排序相对于其他排序到底在什么数据规模下有优势、什么规模下性价比不高。我设计的测试逻辑很简单。准备三组数据一组是完全随机的整数数组一组是几乎有序只有少量乱序元素的数组一组是完全逆序的数组。每组数据分别用插入排序、快速排序取随机枢轴和归并排序执行记录耗时每组数据重复多轮取中位数避免一次性抖动影响判断。需要说明的是这个测试不是为了重新发明排序算法而是为了搞清楚归并排序在实际项目里适合用于什么规模的数据。测试环境就是普通的个人电脑没有做任何底层级优化。5.2 实测结果与几个值得注意的现象测试结果大致如下数据规模从1万到20万不等数据规模插入排序快速排序归并排序1万随机约几十毫秒约几毫秒约几毫秒5万随机明显变慢稳定增长比快排略慢20万随机不可用约几十毫秒约几十毫秒20万近乎有序极快较快与随机时接近有两个现象值得展开。第一在近乎有序的数据上插入排序的表现甚至可以超过快排和归并。因为插入排序对逆序度低的数据本来就接近O(n)实测中20万规模几乎有序的数据插入排序只需要极短时间。这验证了一个工程经验不要盲目在任何数据规模都上O(nlogn)算法要结合数据特征去选择。第二归并排序在纯随机数据上随数据规模增长表现稳健但通常略慢于快排。这和理论分析一致归并排序额外多了一次合并写入过程常数因子比快排大。规模越大这个常数差距越明显。但差距是常数级别的复杂度并不改变。5.3 什么时候该选归并排序根据实测和工程经验我自己的选择标准大致是这样的数据规模很小或者几乎有序优先考虑插入排序内存紧张、不要求稳定性优先考虑快速排序数据规模大、要求稳定、或者最坏情况不可接受直接选归并排序数据大到内存放不下必须走外部排序时也必须走归并思路。这个选择标准没有绝对的“最优”因为实际场景里还会混合内存限制、稳定性、并发情况等多重因素。但把归并排序定位成“稳定、可靠、代价是内存”的排序就不会选错大方向。6. 工程落地中的优化与几个大坑6.1 原地归并别乱试很多人学完归并排序后会觉得O(n)的额外空间不满意想实现一个O(1)空间的“原地归并”。这里要非常慎重。原地归并的理论思路是有的比如在合并时使用旋转交换把右半段元素插入到左半段合适位置同时把被挤出的元素右移。这种做法空间上确实节省了但时间上会退化因为元素移动次数大幅增加实测中性能通常比标准归并排序差到一个量级以上而且代码复杂度暴涨非常容易写出边界bug。在我接触过的实际项目里几乎不会碰到必须用原地归并的场景。如果内存非常受限通常的替代方案是改用堆排序它同样是O(1)空间、O(nlogn)时间而且实现稳定。和原地归并相比堆排的信号更清晰、风险更小。6.2 临时数组的复用优化如果坚持使用归并排序有一个立竿见影的优化不要在每次merge时都新建临时数组而是在一开始就创建一个和原数组等长的全局临时数组每次合并都复用同一个临时空间。def merge(arr, temp, left, mid, right): for i in range(left, right 1): temp[i] arr[i] i, j left, mid 1 idx left while i mid and j right: if temp[i] temp[j]: arr[idx] temp[i] i 1 else: arr[idx] temp[j] j 1 idx 1 while i mid: arr[idx] temp[i] i 1 idx 1 while j right: arr[idx] temp[j] j 1 idx 1这个写法的思路发生了变化先把待合并区间的数据复制到临时数组再通过比较临时数组中的元素把结果直接写回原数组。好处很明显整个排序过程只申请一次额外空间避免了反复分配内存带来的开销。在数据规模较大的实测中这个优化可以让归并排序的整体耗时下降两三成。6.3 小规模子数组切换插入排序另一个工程里常用的优化思路是截止阈值。归并排序递归到很深的层级时每个子数组规模已经很小此时继续递归和merge的固定开销反而比直接做插入排序更贵。很多工业级排序实现会选择当子数组长度小于某个阈值比如16或32时改用插入排序完成这个小段的排序。这个优化逻辑其实和快排的同类优化完全一致递归是有函数调用和栈操作开销的而插入排序在很小规模的数据上常数因子极小直接跑反而更优。实测表明这个阈值能有效减少归并排序在中小规模数据上的运行时间。6.4 底层排序库里的归并混合策略如果你去翻开某主流编程语言标准库的排序实现会发现成熟的排序算法很少是“单一算法走到底”。比如针对对象数组的排序很多语言用的正是TimSort这种融合了插入排序与归并思路的混合算法。TimSort的思想和裸归并排序不太一样它先扫描数据中已经有序的“自然段”称为run用插入排序把过短的run扩容到阈值长度然后把这些run按一定规则两两合并。这种设计让它在处理真实世界中常见的“部分有序”数据时性能远好于标准归并排序。这给我的启发是理解归并排序不能停留在“会写递归版”这个层面。它的核心价值在于“合并两个有序序列”这个操作而这个操作在外部排序、多路归并、数据库排序等场景里会被反复作为基础组件使用。学好归并排序真正学到的是合并这个原语。6.5 递归转迭代的一个实用技巧递归版的归并排序虽然直观但在某些受限环境里比如禁止递归、栈空间极小的嵌入式场景可能不适用。这时可以改成自底向上的迭代写法本质上就是先两两合并长度为1的子数组再四四合并长度为2的有序段依次翻倍直到整个数组合并为一段。def merge_sort_iter(arr): n len(arr) temp [0] * n width 1 while width n: for left in range(0, n, 2 * width): mid min(left width - 1, n - 1) right min(left 2 * width - 1, n - 1) if mid right: merge(arr, temp, left, mid, right) width * 2这个版本没有递归调用循环结构一目了然。理解自底向上的归并对理解外部排序里“先排小块再逐层合并”的过程也很有帮助。我自己在面试候选人的时候如果对方能顺手写出迭代版通常说明对归并的过程是真的吃透了而不只是背了代码。实际操作中我个人最深的一点体会是归并排序是“原理简单、边界暗藏”的典型代表。你可以在五分钟内讲清楚它的思想但真到线上环境为了性能、稳定性、内存开销做权衡时处处都是细节。如果有条件建议在本地环境把递归版、迭代版、临时数组复用版都写一遍再配合不同规模的数据跑跑耗时对比——这套动作做完你对归并排序的理解会比单纯看十篇文章都扎实。