1. 集训第07天为什么必须啃下归并排序基础算法集训进行到第07天前面的冒泡、选择、插入排序如果已经让你觉得“排序不过如此”那今天这道坎就是用来敲醒你的。归并排序不是那种背个模板就能糊弄过去的算法它背后牵着分治思想、递归执行流程、额外空间开销、稳定性分析甚至还能顺手解决“逆序对计数”这种面试里常考的经典问题。可以说归并排序是你从“会写排序”走向“理解算法设计”的第一座桥。不少初学者第一次接触归并排序第一反应是“代码好长”“递归看不懂”“为什么要开额外数组”。这些反应太正常了我当年集训时也在递归的回溯过程里绕晕过。但这道坎必须迈过去因为归并排序的思想会反复出现在后续的快速排序、堆排序、二叉树遍历、CDQ分治、线段树合并等更高级的内容里。你提前把归并排序吃透后面学那些东西会轻松一大截。这篇笔记就按我在集训中实际带练的节奏来写先讲清楚归并排序到底在做什么再逐步拆解代码为什么这么写接着用几个真实案例把递归过程走一遍最后把逆序对这个衍生考点一起拿下。内容尽量往底层讲代码给你可以直接抄的版本坑也提前帮你踩平。适合谁看正在刷题的大学生、准备校招的应届生、自学算法的转行者只要你的算法学习路线里有“排序”这一章这篇文章都能帮你少走弯路。已经会写归并排序的人也可以重点看后面的逆序对部分和调试技巧应该能挖到点新东西。2. 归并排序的设计思想分而治之不只是口号2.1 从“合并两个有序数组”说起归并排序的核心动作其实特别朴素把两个已经有序的数组合并成一个更大的有序数组。举个最直白的例子你有两个数组左半部分[1, 3, 5]右半部分[2, 4, 6]合并逻辑很简单——两个指针分别指向两个数组的头部比较指针所指元素谁小就先把谁放进结果数组然后对应指针后移。哪边先走完就把另一边剩下的元素直接追加到结果末尾。这个过程的时间复杂度是O(n)而且整个合并过程中每个元素只被比较和移动一次非常高效。真正的难点在于怎么让左右两个半部分各自有序答案就是递归。你先把数组从中间劈成两半对左半部分调用归并排序再对右半部分调用归并排序等两半都各自有序了再执行上面说的合并操作。这就形成了“先分解、再解决、后合并”的分治三步曲。用一句话概括归并排序先把数组不断对半拆拆到只剩一个元素天然有序再在回溯过程中两两合并最终得到完整有序数组。这个过程不依赖任何交换操作纯粹靠“拆分合并”完成排序这是它和前面学过的那些基于交换的排序算法最本质的区别。2.2 为什么不用原地合并刚学归并排序时很多人会问同一个问题既然合并是核心操作那能不能直接在原数组上做不申请额外数组这里要说明白一个事实——经典的归并排序在合并阶段必须使用额外空间因为合并过程中你需要同时保留左右两个子数组的原始状态。举个例子就明白了如果直接在原数组上合并[1,3,5]和[2,4,6]把较小的2写到位置0上这时原来的1就被覆盖了后续比较就乱了套。所以必须先把两个待合并的子数组复制到临时空间再在原数组位置上从前往后覆盖写入。这也就是归并排序空间复杂度为O(n)的根本原因。不过你完全不用为此感到焦虑因为这是归并排序为了获得稳定性和稳定O(n log n)时间复杂度的必要代价。实际工程中如果内存充足这个空间开销是完全可接受的。面试时能主动说出“归并排序的空间复杂度是O(n)因为合并时需要额外数组暂存数据”这本身就是加分项。2.3 稳定性归并排序的隐藏优势排序算法的稳定性指的是如果两个相等元素的相对顺序在排序前后不变那这个排序算法就是稳定的。这个性质在普通数值排序时没人在意但当你按多个字段排序时就变得很关键。比如一个对象数组先按姓名排序再按年龄排序那就要求第二次排序不能打乱第一次排序的结果这时候必须用稳定排序。在归并排序中合并时如果左右两边的元素相等我们总是优先取左边的元素这样相等元素的相对顺序就被保留了。代码上只需要把写成合并判断的条件即可。对比一下快速排序是不稳定的堆排序也是不稳定的稳定的排序算法里性能最优的基本就是归并排序。所以Java的Collections.sort()对对象数组默认使用归并排序的变体TimSort正是看中了它的稳定性。3. 代码实现逐步拆解从伪码到可跑版本3.1 C版本面试手写主力C是算法面试最常见的语言归并排序的C写法也最经典。下面的实现我用的是“临时数组全局复用”的思路避免在递归过程中反复申请内存这是一个性能优化点也是很多教科书版本没讲清楚的细节。#include vector using namespace std; void merge(vectorint arr, int left, int mid, int right, vectorint temp) { 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 (int idx left; idx right; idx) { arr[idx] temp[idx]; } } void mergeSort(vectorint arr, int left, int right, vectorint temp) { if (left right) { return; // 只剩一个元素或空天然有序 } int mid left (right - left) / 2; // 防溢出写法 mergeSort(arr, left, mid, temp); // 排序左半部分 mergeSort(arr, mid 1, right, temp); // 排序右半部分 merge(arr, left, mid, right, temp); // 合并两个有序部分 }注意mid left (right - left) / 2这个写法它等价于(left right) / 2但当left right超过int上限时不会溢出。刷题平台上数组长度经常到10^5甚至10^6级别虽然直接加也不至于溢出但养成用防溢出写法的习惯总能避免边界场合的意外。调用方式也很直观vectorint arr {5, 2, 6, 1, 3, 9, 4}; vectorint temp(arr.size()); mergeSort(arr, 0, arr.size() - 1, temp);这里每次递归都带着temp数组走而不是在merge函数内部临时创建。如果每次合并都新建一个vector递归层数一深内存分配的耗时非常可观在LeetCode等平台上可能会导致超时。这个优化非常重要笔试时经常就是这种细节决定了你到底是AC还是TLE。3.2 Python版本逻辑清晰但要注意切片陷阱Python写归并排序最大的优势是代码可读性高最大的坑是切片操作arr[left:right]会产生新列表导致时间复杂度和空间复杂度的成倍增加。下面这种经典实现看起来简洁但如果你在性能敏感的场合用就会吃亏def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result这种写法的问题在于每一层递归都会创建新的左右子列表和结果列表总的空间消耗远不止O(n)常数也很大。对于算法学习来说用这种版本理解归并排序的逻辑完全没问题但如果要刷题我建议用下面这种“在原数组上做合并”的写法def merge_sort(arr, left, right, temp): if left right: return mid (left right) // 2 merge_sort(arr, left, mid, temp) merge_sort(arr, mid 1, right, temp) i, j, k left, mid 1, left while i mid and j right: if arr[i] arr[j]: temp[k] arr[i] i 1 else: temp[k] arr[j] j 1 k 1 while i mid: temp[k] arr[i] i 1 k 1 while j right: temp[k] arr[j] j 1 k 1 for idx in range(left, right 1): arr[idx] temp[idx] # 使用示例 arr [5, 2, 6, 1, 3, 9, 4] temp [0] * len(arr) merge_sort(arr, 0, len(arr) - 1, temp) print(arr) # [1, 2, 3, 4, 5, 6, 9]这个版本用下标索引控制范围不会产生额外的列表切片空间上只多一个temp数组行为也更接近C版本。Python刷题时用这个版本性能会稳很多。3.3 递归流程可视化以实际数组走一遍光贴代码不演示过程等于白贴。我们用[5, 2, 6, 1, 3]这个数组完整走一遍归并排序的递归流程第一步初始调用mergeSort(arr, 0, 4)计算mid 2数组被划分为左半部分[5, 2, 6]右半部分[1, 3]第二步对左半部分调用mergeSort(arr, 0, 2)计算mid 1划分为[5, 2]和[6]先处理[5, 2]调用mergeSort(arr, 0, 1)mid 0划分为[5]和[2]两个单元素数组直接返回合并后得到[2, 5][6]是单元素直接返回与[2, 5]合并得到[2, 5, 6]第三步对右半部分调用mergeSort(arr, 3, 4)mid 3划分为[1]和[3]合并得到[1, 3]第四步最后合并[2, 5, 6]和[1, 3]2和1比1小放12和3比2小放25和3比3小放35剩下放5再放6最终结果[1, 2, 3, 5, 6]整个过程中最关键的理解点是合并的前提是左右两半都已经有序。当你递归到最深层时每个子数组都只有1个元素它天然有序所以合并动作从最底层一步步向上每合并一次有序子数组的长度就翻倍。你的大脑只需要模拟两层递归就够了再深就画递归树而不是在脑子里硬转。这里分享一个我集训时给学生推荐的方法找一张纸把一个8元素数组的递归拆分图画出来一定画到每个叶子节点为止。看起来费时间但只要你亲手画过一次递归的执行顺序就会刻在脑子里比看十遍代码都管用。4. 复杂度分析与工程应用深度解读4.1 时间复杂度为什么稳定在O(n log n)归并排序的时间复杂度可以用递推公式表达。设T(n)表示对n个元素排序所需的时间那么T(n) 2 * T(n/2) O(n)这个公式的含义是对n个元素排序等于对两个n/2的子数组排序也就是2*T(n/2)再加上一次合并的开销O(n)。用主定理直接算结果是T(n) O(n log n)。关键在于归并排序的时间复杂度与输入数据的初始状态无关。无论输入是完全逆序、完全乱序还是已经有序归并排序都严格走完“拆分-合并”全流程比较次数都是相同的量级。这一点和快速排序形成鲜明对比——快排在有序输入下如果不做随机化处理会退化成O(n²)。每次拆分都是对半切所以递归树的层数是log₂n层每层的合并操作总计处理n个元素总工作量就是n乘以log₂n。这个结论值得你记牢面试时说“归并排序时间复杂度稳定在O(n log n)因为每次合并都是线性扫描递归树有log n层”已经很够用了。4.2 空间复杂度O(n)额外数组和递归栈归并排序的空间复杂度由两部分组成合并用的临时数组长度等于原数组O(n)递归调用栈的深度递归树高度log₂n每层占用常数空间O(log n)总空间复杂度取最大项也就是O(n)。很多人会误以为归并排序空间复杂度是O(log n)只算了递归栈而忘了临时数组这是面试中的高频错误点。我和学生模拟面试时至少有一半人在这上面栽过。不过前面说过的“临时数组全局复用”可以让额外空间只分配一次而不是每层递归都分配。虽然空间复杂度的量级不变但实际内存占用和分配开销会少很多。这也是工程代码和教学代码之间一个非常典型的区别。4.3 外部排序归并排序真正的用武之地学归并排序时大家最常问的另一个问题是这东西除了考试和面试实际工程中到底用在哪最经典的答案是外部排序——当数据量大到无法全部装载进内存时归并排序几乎是唯一的选择。外部排序的基本思路是先把大文件切成若干个小块每个小块都能完整加载到内存中用内部排序算法排好序后写回磁盘然后对这些已排序的小块做多路归并逐段读入内存合并最终生成一个全局有序的大文件。这个过程底层用的合并逻辑就是归并排序中那个朴素的双指针合并操作的超级放大版。还有一个典型案例是数据库的排序操作。当SQL查询里出现ORDER BY如果排序数据量超过了数据库配置的内存阈值数据库就会切换到外部排序模式利用临时文件完成排序。这就是归并排序思想的工业级应用。另外前面提到的Java TimSort——它其实是一种融合了归并排序和插入排序的混合算法大量应用于Java标准库和Python的sorted()函数中。4.4 链表排序归并排序的额外优势数组排序时归并排序需要额外O(n)的空间这算它的短板。但如果你要排序的是链表这个短板就消失了——链表不需要额外数组来暂存数据只需要改变节点指针的指向即可完成合并。链表归并排序的思路也很清晰用快慢指针找到链表的中点递归排序左右两半然后不断比较两个链表的头节点把较小的节点接到结果链表尾部。整个过程的空间复杂度只取决于递归栈深度为O(log n)。这个知识点在面试中出现频率不低尤其是那种要求“用O(n log n)时间复杂度排序链表”的题目几乎只能用归并排序完成。5. 归并排序的经典变体逆序对计数5.1 什么是逆序对所谓逆序对就是数组中一对下标(i, j)满足i j但arr[i] arr[j]。简单说就是两个数字“顺序反了”。比如数组[3, 1, 2]中逆序对有(3,1)和(3,2)共2对。而[1, 2, 3]这个完全有序的数组没有逆序对[3, 2, 1]则有3对。求逆序对数量的暴力解法是两层循环逐一比较时间复杂度O(n²)。当n到10^5量级时这个做法基本跑不动。而归并排序可以在排序过程中顺手统计逆序对数量时间复杂度仍然是O(n log n)这是归并排序最经典的衍生考点。5.2 归并排序如何顺带统计逆序对关键在于合并阶段的那个比较动作。当我们在合并两个有序子数组时如果右半部分的元素arr[j]小于左半部分的arr[i]那说明arr[j]这个元素比左半部分从i到mid的所有元素都小因为左半部分有序这中间一共有mid - i 1个元素都比arr[j]大且它们的下标都小于arr[j]所对应的下标。这mid - i 1对就全部是逆序对。这个逻辑非常精妙常规归并排序里出现右半元素更小的情况时你直接把它放进去就完事了。但只要你停下来想想“为什么它更小”逆序对的数量就顺手算出来了。代码只需要在arr[j] arr[i]的分支里加一行累加操作long long count 0; // 全局或引用传递 void merge(vectorint arr, int left, int mid, int right, vectorint temp) { 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]; count mid - i 1; // 左半部分剩余元素都比 arr[j] 大 } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int idx left; idx right; idx) { arr[idx] temp[idx]; } }注意一个细节判断条件必须写成arr[i] arr[j]不能写成。因为当左右两个元素相等时这个元素不算逆序对应该把左边的元素先放进去保证不重复计数。这是我见过最多的一个错误一不留神就会多算逆序对。5.3 实战案例分析来看一个完整例子数组[7, 5, 6, 4]。递归拆分后最底层的合并发生在这几个阶段先排序左半[7, 5]合并时i0指向7j1指向55小于7计数加mid - i 1 0 - 0 1 1得到逆序对(7,5)。合并结果[5, 7]。再排序右半[6, 4]合并时4小于6计数加1得到逆序对(6,4)。合并结果[4, 6]。最后合并[5, 7]和[4, 6]初始i0指向5j2指向44小于5计数加mid - i 1 1 - 0 1 2得到逆序对(5,4)和(7,4)。继续i0指向5j3指向65小于6正常放5。i1指向7j3指向66小于7计数加1 - 1 1 1得到逆序对(7,6)。总计逆序对数量为1 1 2 1 5。可以用暴力法验证[7,5]、[7,6]、[7,4]、[5,4]、[6,4]正好5对。这道题在LeetCode上的编号是剑指Offer 51题目原文就是“数组中的逆序对”很多大厂笔试都直接考过原题。建议你把上面这段代码默写三遍直到闭着眼都能写出来。5.4 其他常见变形区间和的个数归并排序的分治思想还能解决一类更隐蔽的问题——区间和计数。比如LeetCode 327题“区间和的个数”要求统计数组中有多少子数组的和落在[lower, upper]区间内。暴力解法要枚举所有子数组O(n²)复杂度直接超时。利用归并排序的解法非常巧妙先计算前缀和数组prefix那么子数组和就等于prefix[j] - prefix[i]。统计满足lower prefix[j] - prefix[i] upper的配对数量这本质上也是统计某种“特殊逆序对”。归并排序在合并阶段不断比较两个有序子数组时可以用双指针在右半部分快速统计满足条件的元素数量整体复杂度降到O(n log n)。这个题属于归并排序应用的进阶场景第一遍学的时候不要求必须弄懂但至少要知道“归并排序不只是排序它可以扩展成各种区间统计的工具”。等你把基础版逆序对吃透了再回头啃这个题会顺畅得多。6. 归并排序与快速排序、堆排序的横向对比6.1 三者核心差异一览学完归并排序后常见的O(n log n)级排序算法你就集齐了三个归并排序、快速排序、堆排序。它们的时间复杂度看起来一样但适用场景差异很大。我整理过一张对比表每次集训都会发给大家对比维度归并排序快速排序堆排序时间复杂度O(n log n)平均O(n log n)最坏O(n²)O(n log n)空间复杂度O(n)O(log n)递归栈O(1)稳定性稳定不稳定不稳定关键优势稳定、性能可控常数小、效率最高空间省、无递归关键劣势额外空间大最坏情况不稳定常数较大、不稳定典型场景链表排序、逆序对、外部排序常规数组快排大数据量TopK快速排序的平均性能确实是三者中最强的因为它每次分区后数据会逐步逼近有序状态且元素访问的局部性好缓存命中率高。但它的软肋是当输入近似有序时如果选取的基准值不合理时间复杂度会退化到O(n²)所以工程实现中通常要加“三数取中”或“随机基准”来防止退化。堆排序的空间优势无与伦比原地完成排序但它交换元素时破坏了稳定性而且堆操作的常数比较大实际运行速度往往比快排慢。归并排序则牺牲了空间换来了稳定性和可控性在对稳定性有要求或者数据无法全部装入内存的场景下是不可替代的。6.2 实战中怎么选面试和工程中选哪个排序算法其实有一套成熟的判断逻辑如果排序对象是普通的数值数组不要求稳定性优先用快速排序效率最高如果排序对象是对象数组要求相等元素的相对顺序保持不变用归并排序或其变体如果排序对象是链表首选归并排序因为链表不支持随机访问快排的partition操作在链表上实现麻烦且效率低如果内存极度受限比如嵌入式系统堆排序的O(1)空间优势是决定性的如果数据量超过内存容量只能外部排序这本质上就是归并排序的舞台另外提醒一点实际开发中大多数语言的标准库排序函数都已经经过高度优化基本不需要自己手写排序。但算法面试考的是你是不是真的理解底层原理所以这些排序算法的代码依然需要能随手写出来。7. 集训第07天的常见问题与调试实录7.1 递归边界条件搞错我几乎每次带集训都会遇到有学员在递归的边界条件上翻车。最常见的错误是把if (left right) return;写成if (left right) return;。单独看好像没毛病但当你调用mergeSort(arr, 0, 0)时left right可以正常返回可一旦出现left right的情况比如空数组调用mergeSort(arr, 0, -1)left right的写法就永远不会成立函数就会死循环或者越界。安全写法永远是if (left right) return;把空区间和单元素区间统一处理。写递归函数时边界条件宁可写得更宽松一些也不要让它漏掉任何可能的情况。7.2 合并阶段忘记回写临时数组合并完成之后必须把临时数组的内容复制回原数组这一步漏掉的话当前层排序的结果就丢了。这个错误通常在递归层数深的时候才暴露表现为“局部有序但整体乱序”。排查技巧在merge函数的最后加一句断言assert(isSorted(arr, left, right))或者直接打印merge前后的数组内容一眼就能看出问题出在哪一层。如果还没学会断言的调试方法最简单的做法是在关键位置写cout或print输出中间结果结合递归树对照着看问题会非常明显。7.3 临时数组每次递归都新建这是性能问题。很多教程写法是在mergeSort函数内部创建临时数组比如vectorint temp(right - left 1);递归调用会执行log n层每层都创建一次新数组总的空间分配次数非常多。数据量小的时候无所谓数据量大到10^6级别时频繁的内存分配会显著拖慢程序。更规范的工程写法是在最外层创建好临时数组然后通过参数传递进去复用前面给出的C代码就是这个思路。7.4 逆序对数量用int存储导致溢出当数组长度n在10^5级别并且完全逆序时逆序对数量接近n*(n-1)/2也就是大约5×10^9早就超过了int的上限2^31-1。如果用了int去累加计数结果就会溢出变成负数输出完全不对。正确做法是使用long long类型计数这个坑我在带学生刷LeetCode 51时几乎每次都能遇到。7.5 递归深度造成栈溢出怎么办归并排序的递归深度是log₂nn为10^6时递归深度大约20层这在现代编译器和操作系统下完全不会栈溢出。如果你遇到栈溢出的报错大概率不是归并排序本身的问题而是你的递归函数里在栈上放了大数组比如在函数内部直接声明了vectorint temp(right - left 1)。解决办法就是把这个大数组从函数内部挪出来或者改成堆分配。有一种情况是某些在线评测平台开启了栈限制比较严格这时候你也可以改用非递归实现。归并排序的迭代实现其实不复杂从长度为1的子数组开始逐步归并长度为2、4、8……的子数组用循环代替递归。这个版本在你熟练掌握递归版后花半小时就能搞定这里不展开贴代码当作课后练习。8. 集训之外归并排序还能怎么扩展归并排序的分治框架是算法学习中的一座金矿除了逆序对和区间和还有几个常见的扩展方向值得你花时间探索。第一个是求数组中的“重要逆序对”。LeetCode 493题定义的重要逆序对要求arr[i] 2 * arr[j]也就是右半元素必须小于左半元素的一半才算数。解法思路和标准逆序对基本一致只是在合并阶段做统计时不是直接用arr[j] arr[i]判断而是用arr[i] 2 * arr[j]。要在合并循环之外单独做一次双指针统计因为标准合并逻辑会同时移动两个指针没法满足这种带条件的统计需求。第二个是“计算右侧小于当前元素的个数”。LeetCode 315题要求对数组每个元素统计它右边有多少个元素比它小。这个题目直观上和逆序对是同一个问题——标准逆序对统计的是全局数量这道题要求的是每个位置各自的数量。解法是给每个元素带上原始下标在归并过程中统计被“跨越”的次数最后按原始下标回填结果。这道题综合考察了分治、索引映射和归并排序理解属于中高难度题。第三个是归并排序在外部排序中的扩展。前面提到过当数据量大到内存装不下时归并排序就是解决方案。工程上的多路归并不是简单的两两合并而是一次合并k个有序块这种场景通常用败者树或堆来优化选择最小值的过程。这个方向太工程化了校招面试不太会深入考察但如果你有大数据相关的实习经历了解多路归并的原理会很有帮助。建议你把这三个题目收藏好等基础版的归并排序和逆序对都掌握扎实后一个一个去刷。每个题背后牵出的思考方式都会让你对“分治”这两个字有更立体的理解。最后分享一点我自己的教学体会归并排序是第一道真正需要你“拆开来看”的排序算法。冒泡排序、插入排序你盯着代码看几秒钟就能明白它在干什么但归并排序不一样你只有把递归拆成树形结构把每一层的合并动作在纸上画出来才能建立真正的直觉。这个过程没法跳过也没有捷径。等你哪一天不看代码就能在脑子里完整走完一个乱序数组的归并全过程那这一关你就算真正过了。后面再学快速排序你会发现它的分治思路其实和归并排序一脉相承区别只在于“先分区再递归”和“先递归再合并”的次序差别学起来会顺手得多。