复杂度推导)
任何一个认真啃过《算法导论》的人应该都对“分治法”这个章节记忆犹新。不光是因为合并排序Merge Sort也叫归并排序作为第一个完整展示分治思想的经典算法被反复剖析更是因为这一章第一次让你感受到“把一个复杂问题拆碎再逐个击破并合并结果”这种思路带来的智商碾压感。说实话我在学校里第一次看到合并排序的递推树展开时才真正理解什么叫“算法设计决定程序性能”。这篇东西不是贴一堆代码就完事我想把分治法的骨架、合并排序的实现细节、复杂度推导过程以及我在实际调试和面试里踩过的坑一次性讲透。这篇文章适合谁看如果你是刚接触算法的学生可以用它把“分治法到底在干什么”彻底搞明白如果你准备面试合并排序和它的变形题逆序对统计、链表排序是高频考点如果你在工作里偶尔需要写点排序逻辑这篇文章也能帮你搞清楚什么时候该选归并排序什么时候该躲开它。1. 分治法的核心思想拆解分治法不是某一种具体的算法而是一类解决问题的思路。它的框架就三步分解Divide、解决Conquer、合并Combine。但很多人读了定义还是蒙“这不就是递归吗”对它确实依托递归实现但分治法和普通递归最大的区别在于——分解之后的问题必须互相独立、规模更小、并且合并结果有明确规则。只有这三个条件都满足才谈得上分治。我说的通俗一点。想象你面前有一副乱掉的扑克牌你要把它按顺序排好。最笨的办法是从头到脚挨个找最小牌找出来再找次小牌这种是插入排序的思路。分治法的思路是完全反过来的先把牌堆一分为二再一分为二直到每堆只剩一张牌。一堆只有一张牌那它天然就是有序的。然后你把两堆各一张的牌合并成一组两张的有序牌再把两组两张的合并成一组四张的……最后整副牌就有序了。这里有个关键点容易被忽略分治法的效率提升靠的不是“分”本身而是“合并”的成本足够低。你分解得再漂亮如果合并时要付出巨大的代价那整体效率照样不行。合并排序之所以优秀正是因为它的“合并”过程可以在线性时间内完成——这个点我在第2部分详细拆。还有一个容易忽略的点分治法的递归深度问题。你每次把规模除以某个常数那递归深度就是对数级别的。归并排序每次对半分深度就是 log₂(n)。这是它优于很多递归算法比如某些深度可达 n 的递归遍历的地方。我见过不少初学者担心递归太慢其实真正影响性能的往往是递归深度过大导致的栈溢出而不是递归本身。你设计分治方案时第一件事就是确认“每次分解的规模缩减因子是不是固定常数”。1.1 为什么拆分后反而更快复杂度直觉很多人会有个疑问把排序一个 n 长度数组的问题拆成两个 n/2 的子问题两个加起来的规模不还是 n 吗也没少干活啊怎么就变快了呢这里的关键在于局限复杂度只关注“问题规模”还不够得看总工作量随规模增长的速度。我们拿插入排序做对比。插入排序每处理一个新元素可能要跟前面所有已排序的元素比较所以它的工作量大约是 123…n ≈ n²/2是平方量级。归并排序则是每个元素在“合并”阶段最多被比较并搬动 log₂(n) 次因为共有 log₂(n) 层合并所以总量是 n × log₂(n) 量级。用一个具体数据感受一下。n100万时n² 1万亿n log₂ n ≈ 2000万。差了五万倍。所以“拆分”的意义在于通过分层处理把你的总工作量从“平方爆炸”压低到“对数缓增”。1.2 分治思想在生活中的类比我总爱拿整理会议记录来打比方。假设你手里有一堆没排序的报销单据你要把它按日期排好。人工排序时有个天然困境单据太多脑子装不下同时比较所有元素。分治法解决的就是这个困境——你不需要同时记住所有单据你只需要每次面对两个已经排好的小堆每次二选一取出较小的一张大脑的负担就小很多。这就是为什么归并排序特别适合“内存放不下大数组、需要借助外存分块处理”的场景比如大数据量外部排序。如果你在学操作系统或数据库会发现外部排序的基本思路就是归并排序的变体数据先分块排序到磁盘然后多路归并成一个整体有序的大文件。所以说归并排序的“分治”思想价值远不止排序本身。2. 合并排序的原理与完整实现先把合并排序的完整逻辑理清。整个过程简单到可以浓缩成一句话递归地把序列对半拆到只剩一个元素然后把相邻的有序小段两两合并直到整个序列有序。但这句话里藏了两个极其重要的细节。第一为什么拆到只剩一个元素就停因为单个元素天然有序不需要再做比较。第二合并两个有序子序列的方式是什么——这其实是一个“二路归并”操作也是整个排序的核心动作。我先把“合并”这个核心动作单独拎出来讲。假设你有两个已经有序的数组 A 和 B要把它们合并成一个有序的大数组 C。做法是用指针 i 指向 A 的头部指针 j 指向 B 的头部指针 k 指向 C 的头部。每次比较 A[i] 和 B[j]把较小的那个放进 C[k]对应指针前进一位。循环直到一边空了把剩下的直接拷贝进 C。因为 A、B 各自有序每次取出的都是当前全局最小值所以最终 C 必然整体有序。2.1 合并操作的直观演示我们用一个很短的例子看合并过程。假设要合并序列 [2, 5, 7] 和 [1, 3, 8]步骤左序列指针位置右序列指针位置比较结果放入结果数组1211 较小[1]2232 较小[1, 2]3533 较小[1, 2, 3]4585 较小[1, 2, 3, 5]5787 较小[1, 2, 3, 5, 7]6空8直接拷贝[1, 2, 3, 5, 7, 8]看到没每次比较最多移动一个元素合并两个长度为 n/2 的序列比较次数最多 n-1 次整体是线性的。整个排序的代价就是每一层所有合并段合起来都是 O(n)一共 log₂ n 层所以总复杂度 O(n log n)。2.2 完整实现代码Python 版本我平时讲归并排序最喜欢用 Python 演示因为可读性好。先来一个最符合脑内模型的版本def merge_sort(arr): if len(arr) 1: return arr # 分解找中点 mid len(arr) // 2 left arr[:mid] right arr[mid:] # 递归解决对左右两半分别排序 left merge_sort(left) right merge_sort(right) # 合并把两个有序序列合并成一个 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 # 谁有剩余就全部追加 if i len(left): result.extend(left[i:]) if j len(right): result.extend(right[j:]) return result这段代码的逻辑非常清晰从小到大对分、递归、合并。但你有没有发现它每一步都在创建新的列表。这在教学上完全没问题在工程上就是灾难——大量额外的内存分配和拷贝会让性能打折扣。所以真正写高性能归并排序我们会用原地辅助数组的方式。2.3 原地辅助数组版本C 风格归并排序的“原地”不是真正意义上完全不额外开空间而是只使用一个与原始数组等大的辅助数组通过下标控制在辅助数组和原数组之间来回拷贝避免反复 new 数组。我给出一版工程上更常用的写法void merge(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; // 左半部分起点 int j mid 1; // 右半部分起点 int k left; // 临时数组起点 // 把两个有序段合并到临时数组 temp 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 都很大的时候left right 可能整型溢出这个坑我在面试题里见过不止一次。第二每次合并完成后必须把临时数组对应区间拷贝回原数组否则下一轮合并时用的就是脏数据。2.4 哨兵Sentinel优化技巧还有一个值得掌握的优化不过在 merge 过程中加一个“哨兵”值也就是在左右两个序列末尾加一个无穷大的占位值这样就不需要再判断某一侧序列是否为空了。void mergeWithSentinel(vectorint arr, int left, int mid, int right, vectorint temp) { // 拷贝左半部分到 temp for (int i left; i mid; i) temp[i] arr[i]; // 拷贝右半部分到 temp顺序反过来放方便两端向中间取 for (int j mid 1; j right; j) temp[j] arr[right - (j - (mid 1))]; int i left; int j right; for (int k left; k right; k) { if (temp[i] temp[j]) { arr[k] temp[i]; } else { arr[k] temp[j--]; } } }上面这段用了一个小技巧右半部分在临时数组中倒序存放这样从两端向中间取值左右两侧分别从 left 向右、从 right 向左移动就天然实现了“当某一侧到头时另一侧的值一定都更小”的效果省掉了越界判断。这种写法在《算法导论》里有提到实际写竞赛代码时很受用。不过坦率说哨兵版本可读性不如最基础的版本我建议你先把基础版本练熟再考虑优化。工程里绝大多数情况下最基础的 merge 写法就够了真正性能瓶颈往往在递归深度和系统栈而不是那几次越界判断。3. 递归树与复杂度推导为什么是 O(n log n)既然题目叫《算法导论-分治法和合并排序》那复杂度推导就是绕不开的重点。这部分我们不能只记住结论得推导一遍。3.1 递推式的建立设 T(n) 是排序 n 个元素所需的时间。分治过程包含三部分分解需要 O(1)算个中点递归解决两个规模为 n/2 的子问题时间是 2T(n/2)合并两个子序列最坏情况下需要 n-1 次比较是 O(n)。所以递推式是T(n) 2T(n/2) O(n)T(1) O(1)这个递推式你展开一下T(n) 2T(n/2) n 2[2T(n/4) n/2] n 4T(n/4) 2n 8T(n/8) 3n …当规模降到 1 时经过了 k 层n/2^k 1k log₂ n。那么 T(n) nT(1) kn 1×n (log₂ n)×n O(n log n)。所以归并排序的最坏、最好、平均时间复杂度都是 O(n log n)这一点和快速排序不同快速排序最坏能退化到 O(n²)而归并排序因为结构固定是均匀二分永不退化。3.2 递推树的可视化推演如果你觉得展开递推式太抽象可以画一棵递推树。树的根节点代表对长度为 n 的序列做合并消耗 O(n)根节点分出两个子节点每个对应长度为 n/2 的序列合并每个消耗 O(n/2)两个合起来一层消耗 O(n)再往下四个长度为 n/4 的节点每层加起来还是 O(n)。整棵树的高度是 log₂ n所以每层 O(n) × 层数 log₂ n O(n log n)。这就是分治法最优雅的地方每一层的总工作量不随层数增加而膨胀始终是 O(n)。对比快速排序快排在极端失衡的情况下每层的工作量可能不再是均匀的 n递归树也会偏斜成一条链从而退化为 O(n²)。分治法的“平衡”是效率的灵魂后来很多算法如块状链表、treap 的按规模分裂设计时都在追求这种平衡性。3.3 空间复杂度不得不提的代价归并排序的空间复杂度是 O(n)因为每层递归中合并过程需要一个长度为 n 的临时数组。有一些优化版本比如原地归并排序能把额外空间压到 O(1)但代价是合并过程复杂度退化到 O(n log n)总复杂度反而变成 O(n² log n)得不偿失。所以工程上基本默认接受 O(n) 的空间额外开销。这里要注意一个实现细节如果每次递归都新建临时数组那么递归过程中同时存在的临时数组空间总和是 n n/2 n/4 … 2n这也是 O(n)但频繁分配释放的常数开销很大。所以真正高效的实现里临时数组都是在递归入口一次性开辟然后通过下标传递也就是我在 2.3 节写的那个版本。这一点笔试面试是要考的很多人不知道。3.4 与其他排序的对比我整理了一张常用排序算法的对比表面试前可以默念一遍排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定稳定性是个经常被忽略的指标。归并排序是稳定的也就是说如果两个元素的值相等排序后它们的相对前后顺序不会改变。这在某些场景下是硬需求——比如你有一批按“姓名”排好序的数据现在要按“部门”排序同时希望部门内部的人仍然保持姓名字典序。用归并排序就能轻松做到因为相等元素不会交叉。HashMap、TreeMap 里有不少内部排序逻辑选用的就是稳定排序思想。4. 从思路到代码核心环节的落地与调试前面给了核心代码但代码能跑通和代码写得对、写得稳是两回事。这一节我把从思路到代码的完整落地过程过一遍尤其是我在调试过程中踩过的坑。4.1 递归终止条件到底怎么设置归并排序的递归终止条件是left right。我见过不少初学者写成left right这也能跑但如果在递归调用时不小心写成了mergeSort(arr, left, mid)和mergeSort(arr, mid, right)注意右边界没减一就可能导致无限递归——因为当 mid right 时右边区间没缩小永远循环下去。所以建议统一写成left right并且统一用闭区间[left, right]来管理。如果你用我跟学生交流时常说的一个口诀来记闭区间 [left, right]取中 mid (left right) / 2左半边是 [left, mid]右半边是 [mid1, right]。别小看这个约定它在二分查找、线段树、分治算法里都是通用的统一能减少无数 bug。4.2 一个典型错误越界写入我调过一份代码bug 表现为“排序结果里偶尔多出垃圾值”。最后定位到问题出在合并时某个子序列已经取完了但代码还在继续访问它的下一个下标导致越界读。如果你用的是基础 merge 写法合并逻辑必须写成“两个子序列都还有元素时才比较一方空了就直接拷贝另一方剩余部分”。顺序不能反否则轻则数据错乱重则数组越界。好的习惯是在 merge 函数的入口处加一个断言确认 left mid right并且传入的 temp 数组下标范围够用。面试时你说一句“我会在最开始做一个边界检查”面试官对你的印象分会好很多。4.3 递归层级太深怎么办如果待排序数组长度是 100 万递归深度是 log₂(100万) ≈ 20完全没压力。但如果你在 Java 里默认的递归栈不够或者你处理的是链表结构而链表的递归实现又每家写法不同可能在 10 万级数据时就开始出问题。我自己的经验是真正工作里归并排序处理几十万数据都不会栈溢出真正害怕栈溢出的是快速排序这种可能退化的递归。如果你实在担心可以把归并排序改成自底向上的迭代版本。自底向上的归并排序思路也不难先合并长度为 1 的相邻段得到长度为 2 的有序段再合并长度为 2 的相邻段得到长度为 4 的有序段以此类推。迭代版本不需要递归也就不存在栈溢出问题。代码如下void mergeSortIterative(vectorint arr) { int n arr.size(); vectorint temp(n); for (int width 1; width n; width * 2) { for (int left 0; left n - 1; left 2 * width) { int mid min(left width - 1, n - 1); int right min(left 2 * width - 1, n - 1); // 复用之前定义的 merge 函数 merge(arr, left, mid, right, temp); } } }注意width * 2可能会溢出要是 n 很大建议写成width min(width * 2, n)或者干脆用 long 类型。这个细节一般不致命但严谨一点没坏处。4.4 性能实测递归和迭代哪个快我在自己机器上对一个 100 万随机整数的数组做了测试递归版本比迭代版本快了大约 10%。原因可能是递归版本天然有更好的局部性每一层对内存的访问模式更贴近 CPU 缓存而迭代版本外层循环跳跃范围较大缓存命中率略差。但这一点在不同语言、不同编译器下差异很大我建议你在自己的环境里实测别盲目相信网上的结论。工程上如果数据规模上亿我会利用并行流或者多线程对左右子数组分别排序再合并这样能进一步压榨多核性能。5. 归并排序的高频变体与应用场景归并排序本身是一个完整的算法但它之所以能在算法面试和工程中占据一席之地很大一部分原因是它衍生出的几个变体直接映射了现实问题。我挑三个最高频的展开。5.1 求逆序对数量逆序对指的是数组中满足 i j 且 arr[i] arr[j] 的两元组(i, j)。暴力求解是 O(n²)但如果用归并排序可以在合并过程中顺带统计逆序对数量总时间依然是 O(n log n)。核心洞察是合并两个有序子序列时如果右半部分的某个元素 arr[j] 比左半部分的 arr[i] 小那么左半部分从 i 到 mid 的所有元素都大于 arr[j]这些都能和 arr[j] 形成逆序对。因此在 merge 中发现arr[i] arr[j]时把mid - i 1累加到答案里即可。这个题的变体在各大厂笔试里反复出现因为它考察的不只是会不会背归并排序而是能不能理解归并过程中“比较次序”背后的信息量。我个人建议你把逆序对统计的代码亲手写一遍比单纯看十遍都管用。5.2 链表的 O(n log n) 排序数组排序随便写但链表排序就不一样了。因为链表不支持随机访问很多依赖下标的排序算法快排、堆排很难直接实现而归并排序对链表的适应性极好——你只需要找到中点快慢指针递归排序两段然后做链表的合并。合并不需要额外空间只需要修改 next 指针。实现时有两个细节。第一找中点用快慢指针快指针每次走两步、慢指针每次走一步快指针到末尾时慢指针正好在中点。第二在递归时记得把两个子链表断开否则合并时可能无限循环。链表归并排序的时间复杂度依旧是 O(n log n)空间复杂度因为递归栈是 O(log n)比数组版更省内存。这是 LeetCode 148 题的标准解法值得背下来。5.3 外部排序当内存装不下数据时如果你要排序一个 100 GB 的文件但内存只有 8 GB全部数据不可能一次载入。这时候就是外部排序登场。经典策略就是归并排序思想的延伸把大文件分块读入内存每块比如 1 GB用普通快排排好写回磁盘。这样得到 100 个有序的小文件分块。从每个分块文件里读入一段数据到内存缓冲区做多路归并不断从缓冲区中选出最小值写入输出文件哪个缓冲区空了就从对应分块继续读。最终合并成一个整体有序的大文件。实际系统的多路归并会用败者树来优化多路选择最小值的效率。但核心思想仍然是“分解-解决-合并”。所以说归并排序是算法课里“学完立刻能用到生产环境”的少数排序算法之一完全不是纸上谈兵。5.4 混合排序Timsort 的启发Java 的 Arrays.sort() 在对对象数组排序时用的是 Timsort一种改良版归并排序它的思想是对于接近有序的序列先用二分插入排序把连续的自然有序片段识别出来然后再用归并操作把它们合并。这种“利用数据本身特点 分治合并”的思路让排序在真实数据上通常比理论最坏情况快得多。我在实际项目中处理一批已经部分有序的数据时也借鉴过这个思路先扫描出天然有序的片段然后只对这些片段做归并性能比单纯的快速排序稳定很多。这就是归并排序思想的生命力——它不是一个孤立的模板而是打开“通过组合数据特征和分治策略解决问题”这扇门的一把钥匙。6. 常见问题与避坑经验速查写归并排序的时候我踩过一些坑也看过很多学生踩坑。这里整理一份清单按“症状-原因-对策”的方式列出希望对你有帮助。症状原因对策结果只是部分有序合并时没比较完直接拷贝全部检查 while 循环条件一方为空后追加剩余部分递归一直不结束导致栈溢出递归边界时区间没缩小检查 mid 计算和递归参数使用闭区间约定合并后原数组没变修改的是临时数组忘了拷贝回来merge 末尾一定要把 temp 区间拷贝回原数组大数组排序很慢每次递归现建临时数组改为外部一次性申请 temp递归时通过下标复用数组值重复时顺序乱掉合并条件写成了而不是相等时必须让左半部分先放入保证稳定性整型溢出导致中点算错left right 溢出mid left (right - left) / 2还有一个容易被忽略的调试技巧排序算法写完不要直接拿大规模数据测试。先写一个暴力排序比如 Python 的 sorted然后用随机数生成器生成小数组长度 5~20把归并排序结果和暴力排序结果对比不同就打印出输入数组。这样能在几秒钟内定位 bug而不用对着 10 万条调试日志崩溃。这个习惯我一直保留到现在工作里写任何自定义排序逻辑都这么验证效率奇高。另一个实战经验如果你在写归并排序的泛型版本比如 Java 的 Comparator 版本相等元素的处理一定要用否则破坏了稳定性。有人觉得稳定排序无所谓但在真实系统里两个字段连续排序的场景太常见了稳定性直接决定二次排序结果是否正确。7. 从归并排序到分治思维的方法论最后我想聊点学习层面的东西。合并排序本身不难但真正难的是把“分治”这两个字内化成你解决问题的本能。我自己的心得体会是在遇到一个复杂度看起来是 O(n²) 的问题时先别急着优化常数停下来想想三件事第一这个问题能不能拆成两个独立的子问题如果能子问题之间是不是没有重叠没有重叠才有资格用分治如果子问题之间重叠很多比如斐波那契数列的朴素递归那更适合动态规划而不是分治。第二拆完之后合并的代价能不能做到线性或接近线性归并排序成功的前提是合并是 O(n)如果合并本身要 O(n²)那你整个算法还是 O(n² log n) 甚至更糟。分治不是万能的关键在合并成本。第三递归的深度有多大如果每次规模缩减不是固定比例的常数递归树可能会退化成链那样分治就失去了意义。这也是为什么我们设计分治算法时要保证“平衡”分解。学习《算法导论》这一章时我强烈建议不要只盯着归并排序的代码。把书里的“递归式求解”和“主定理”也一并吃透这是理解很多后续高级算法如分治FFT、CDQ分治、整体二分的基础。你越往后学越会发现合并排序只是一个引子分治思想会像杠杆一样放大你的解题能力。如果你是从零开始学算法的读者我的建议是先手写一个无 bug 的递归归并排序数组版再手写一个无 bug 的链表归并排序再做一道逆序对统计题最后打开主定理那一节对着例 4 自己推一遍 T(n) 2T(n/2) n 的展开过程。这一套流程走完你对分治法的理解就不会只是“背模板”而是真正有了肌肉记忆。归并排序是我在面试里最常让候选人手写的一个算法。不是因为它是最高级的排序而是因为从代码风格、边界处理、临时数组的使用到对复杂度的口头推导能一气呵成讲明白的人通常对算法基础都掌握得很扎实。希望这篇东西能帮你也成为那个“一气呵成”的人。 
长河君 · 2026/10/22 11:14:13 · 阅读 1.2k 分治法与合并排序详解：从递归原理到O(n log n)复杂度推导
任何一个认真啃过《算法导论》的人应该都对“分治法”这个章节记忆犹新。不光是因为合并排序Merge Sort也叫归并排序作为第一个完整展示分治思想的经典算法被反复剖析更是因为这一章第一次让你感受到“把一个复杂问题拆碎再逐个击破并合并结果”这种思路带来的智商碾压感。说实话我在学校里第一次看到合并排序的递推树展开时才真正理解什么叫“算法设计决定程序性能”。这篇东西不是贴一堆代码就完事我想把分治法的骨架、合并排序的实现细节、复杂度推导过程以及我在实际调试和面试里踩过的坑一次性讲透。这篇文章适合谁看如果你是刚接触算法的学生可以用它把“分治法到底在干什么”彻底搞明白如果你准备面试合并排序和它的变形题逆序对统计、链表排序是高频考点如果你在工作里偶尔需要写点排序逻辑这篇文章也能帮你搞清楚什么时候该选归并排序什么时候该躲开它。1. 分治法的核心思想拆解分治法不是某一种具体的算法而是一类解决问题的思路。它的框架就三步分解Divide、解决Conquer、合并Combine。但很多人读了定义还是蒙“这不就是递归吗”对它确实依托递归实现但分治法和普通递归最大的区别在于——分解之后的问题必须互相独立、规模更小、并且合并结果有明确规则。只有这三个条件都满足才谈得上分治。我说的通俗一点。想象你面前有一副乱掉的扑克牌你要把它按顺序排好。最笨的办法是从头到脚挨个找最小牌找出来再找次小牌这种是插入排序的思路。分治法的思路是完全反过来的先把牌堆一分为二再一分为二直到每堆只剩一张牌。一堆只有一张牌那它天然就是有序的。然后你把两堆各一张的牌合并成一组两张的有序牌再把两组两张的合并成一组四张的……最后整副牌就有序了。这里有个关键点容易被忽略分治法的效率提升靠的不是“分”本身而是“合并”的成本足够低。你分解得再漂亮如果合并时要付出巨大的代价那整体效率照样不行。合并排序之所以优秀正是因为它的“合并”过程可以在线性时间内完成——这个点我在第2部分详细拆。还有一个容易忽略的点分治法的递归深度问题。你每次把规模除以某个常数那递归深度就是对数级别的。归并排序每次对半分深度就是 log₂(n)。这是它优于很多递归算法比如某些深度可达 n 的递归遍历的地方。我见过不少初学者担心递归太慢其实真正影响性能的往往是递归深度过大导致的栈溢出而不是递归本身。你设计分治方案时第一件事就是确认“每次分解的规模缩减因子是不是固定常数”。1.1 为什么拆分后反而更快复杂度直觉很多人会有个疑问把排序一个 n 长度数组的问题拆成两个 n/2 的子问题两个加起来的规模不还是 n 吗也没少干活啊怎么就变快了呢这里的关键在于局限复杂度只关注“问题规模”还不够得看总工作量随规模增长的速度。我们拿插入排序做对比。插入排序每处理一个新元素可能要跟前面所有已排序的元素比较所以它的工作量大约是 123…n ≈ n²/2是平方量级。归并排序则是每个元素在“合并”阶段最多被比较并搬动 log₂(n) 次因为共有 log₂(n) 层合并所以总量是 n × log₂(n) 量级。用一个具体数据感受一下。n100万时n² 1万亿n log₂ n ≈ 2000万。差了五万倍。所以“拆分”的意义在于通过分层处理把你的总工作量从“平方爆炸”压低到“对数缓增”。1.2 分治思想在生活中的类比我总爱拿整理会议记录来打比方。假设你手里有一堆没排序的报销单据你要把它按日期排好。人工排序时有个天然困境单据太多脑子装不下同时比较所有元素。分治法解决的就是这个困境——你不需要同时记住所有单据你只需要每次面对两个已经排好的小堆每次二选一取出较小的一张大脑的负担就小很多。这就是为什么归并排序特别适合“内存放不下大数组、需要借助外存分块处理”的场景比如大数据量外部排序。如果你在学操作系统或数据库会发现外部排序的基本思路就是归并排序的变体数据先分块排序到磁盘然后多路归并成一个整体有序的大文件。所以说归并排序的“分治”思想价值远不止排序本身。2. 合并排序的原理与完整实现先把合并排序的完整逻辑理清。整个过程简单到可以浓缩成一句话递归地把序列对半拆到只剩一个元素然后把相邻的有序小段两两合并直到整个序列有序。但这句话里藏了两个极其重要的细节。第一为什么拆到只剩一个元素就停因为单个元素天然有序不需要再做比较。第二合并两个有序子序列的方式是什么——这其实是一个“二路归并”操作也是整个排序的核心动作。我先把“合并”这个核心动作单独拎出来讲。假设你有两个已经有序的数组 A 和 B要把它们合并成一个有序的大数组 C。做法是用指针 i 指向 A 的头部指针 j 指向 B 的头部指针 k 指向 C 的头部。每次比较 A[i] 和 B[j]把较小的那个放进 C[k]对应指针前进一位。循环直到一边空了把剩下的直接拷贝进 C。因为 A、B 各自有序每次取出的都是当前全局最小值所以最终 C 必然整体有序。2.1 合并操作的直观演示我们用一个很短的例子看合并过程。假设要合并序列 [2, 5, 7] 和 [1, 3, 8]步骤左序列指针位置右序列指针位置比较结果放入结果数组1211 较小[1]2232 较小[1, 2]3533 较小[1, 2, 3]4585 较小[1, 2, 3, 5]5787 较小[1, 2, 3, 5, 7]6空8直接拷贝[1, 2, 3, 5, 7, 8]看到没每次比较最多移动一个元素合并两个长度为 n/2 的序列比较次数最多 n-1 次整体是线性的。整个排序的代价就是每一层所有合并段合起来都是 O(n)一共 log₂ n 层所以总复杂度 O(n log n)。2.2 完整实现代码Python 版本我平时讲归并排序最喜欢用 Python 演示因为可读性好。先来一个最符合脑内模型的版本def merge_sort(arr): if len(arr) 1: return arr # 分解找中点 mid len(arr) // 2 left arr[:mid] right arr[mid:] # 递归解决对左右两半分别排序 left merge_sort(left) right merge_sort(right) # 合并把两个有序序列合并成一个 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 # 谁有剩余就全部追加 if i len(left): result.extend(left[i:]) if j len(right): result.extend(right[j:]) return result这段代码的逻辑非常清晰从小到大对分、递归、合并。但你有没有发现它每一步都在创建新的列表。这在教学上完全没问题在工程上就是灾难——大量额外的内存分配和拷贝会让性能打折扣。所以真正写高性能归并排序我们会用原地辅助数组的方式。2.3 原地辅助数组版本C 风格归并排序的“原地”不是真正意义上完全不额外开空间而是只使用一个与原始数组等大的辅助数组通过下标控制在辅助数组和原数组之间来回拷贝避免反复 new 数组。我给出一版工程上更常用的写法void merge(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; // 左半部分起点 int j mid 1; // 右半部分起点 int k left; // 临时数组起点 // 把两个有序段合并到临时数组 temp 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 都很大的时候left right 可能整型溢出这个坑我在面试题里见过不止一次。第二每次合并完成后必须把临时数组对应区间拷贝回原数组否则下一轮合并时用的就是脏数据。2.4 哨兵Sentinel优化技巧还有一个值得掌握的优化不过在 merge 过程中加一个“哨兵”值也就是在左右两个序列末尾加一个无穷大的占位值这样就不需要再判断某一侧序列是否为空了。void mergeWithSentinel(vectorint arr, int left, int mid, int right, vectorint temp) { // 拷贝左半部分到 temp for (int i left; i mid; i) temp[i] arr[i]; // 拷贝右半部分到 temp顺序反过来放方便两端向中间取 for (int j mid 1; j right; j) temp[j] arr[right - (j - (mid 1))]; int i left; int j right; for (int k left; k right; k) { if (temp[i] temp[j]) { arr[k] temp[i]; } else { arr[k] temp[j--]; } } }上面这段用了一个小技巧右半部分在临时数组中倒序存放这样从两端向中间取值左右两侧分别从 left 向右、从 right 向左移动就天然实现了“当某一侧到头时另一侧的值一定都更小”的效果省掉了越界判断。这种写法在《算法导论》里有提到实际写竞赛代码时很受用。不过坦率说哨兵版本可读性不如最基础的版本我建议你先把基础版本练熟再考虑优化。工程里绝大多数情况下最基础的 merge 写法就够了真正性能瓶颈往往在递归深度和系统栈而不是那几次越界判断。3. 递归树与复杂度推导为什么是 O(n log n)既然题目叫《算法导论-分治法和合并排序》那复杂度推导就是绕不开的重点。这部分我们不能只记住结论得推导一遍。3.1 递推式的建立设 T(n) 是排序 n 个元素所需的时间。分治过程包含三部分分解需要 O(1)算个中点递归解决两个规模为 n/2 的子问题时间是 2T(n/2)合并两个子序列最坏情况下需要 n-1 次比较是 O(n)。所以递推式是T(n) 2T(n/2) O(n)T(1) O(1)这个递推式你展开一下T(n) 2T(n/2) n 2[2T(n/4) n/2] n 4T(n/4) 2n 8T(n/8) 3n …当规模降到 1 时经过了 k 层n/2^k 1k log₂ n。那么 T(n) nT(1) kn 1×n (log₂ n)×n O(n log n)。所以归并排序的最坏、最好、平均时间复杂度都是 O(n log n)这一点和快速排序不同快速排序最坏能退化到 O(n²)而归并排序因为结构固定是均匀二分永不退化。3.2 递推树的可视化推演如果你觉得展开递推式太抽象可以画一棵递推树。树的根节点代表对长度为 n 的序列做合并消耗 O(n)根节点分出两个子节点每个对应长度为 n/2 的序列合并每个消耗 O(n/2)两个合起来一层消耗 O(n)再往下四个长度为 n/4 的节点每层加起来还是 O(n)。整棵树的高度是 log₂ n所以每层 O(n) × 层数 log₂ n O(n log n)。这就是分治法最优雅的地方每一层的总工作量不随层数增加而膨胀始终是 O(n)。对比快速排序快排在极端失衡的情况下每层的工作量可能不再是均匀的 n递归树也会偏斜成一条链从而退化为 O(n²)。分治法的“平衡”是效率的灵魂后来很多算法如块状链表、treap 的按规模分裂设计时都在追求这种平衡性。3.3 空间复杂度不得不提的代价归并排序的空间复杂度是 O(n)因为每层递归中合并过程需要一个长度为 n 的临时数组。有一些优化版本比如原地归并排序能把额外空间压到 O(1)但代价是合并过程复杂度退化到 O(n log n)总复杂度反而变成 O(n² log n)得不偿失。所以工程上基本默认接受 O(n) 的空间额外开销。这里要注意一个实现细节如果每次递归都新建临时数组那么递归过程中同时存在的临时数组空间总和是 n n/2 n/4 … 2n这也是 O(n)但频繁分配释放的常数开销很大。所以真正高效的实现里临时数组都是在递归入口一次性开辟然后通过下标传递也就是我在 2.3 节写的那个版本。这一点笔试面试是要考的很多人不知道。3.4 与其他排序的对比我整理了一张常用排序算法的对比表面试前可以默念一遍排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定稳定性是个经常被忽略的指标。归并排序是稳定的也就是说如果两个元素的值相等排序后它们的相对前后顺序不会改变。这在某些场景下是硬需求——比如你有一批按“姓名”排好序的数据现在要按“部门”排序同时希望部门内部的人仍然保持姓名字典序。用归并排序就能轻松做到因为相等元素不会交叉。HashMap、TreeMap 里有不少内部排序逻辑选用的就是稳定排序思想。4. 从思路到代码核心环节的落地与调试前面给了核心代码但代码能跑通和代码写得对、写得稳是两回事。这一节我把从思路到代码的完整落地过程过一遍尤其是我在调试过程中踩过的坑。4.1 递归终止条件到底怎么设置归并排序的递归终止条件是left right。我见过不少初学者写成left right这也能跑但如果在递归调用时不小心写成了mergeSort(arr, left, mid)和mergeSort(arr, mid, right)注意右边界没减一就可能导致无限递归——因为当 mid right 时右边区间没缩小永远循环下去。所以建议统一写成left right并且统一用闭区间[left, right]来管理。如果你用我跟学生交流时常说的一个口诀来记闭区间 [left, right]取中 mid (left right) / 2左半边是 [left, mid]右半边是 [mid1, right]。别小看这个约定它在二分查找、线段树、分治算法里都是通用的统一能减少无数 bug。4.2 一个典型错误越界写入我调过一份代码bug 表现为“排序结果里偶尔多出垃圾值”。最后定位到问题出在合并时某个子序列已经取完了但代码还在继续访问它的下一个下标导致越界读。如果你用的是基础 merge 写法合并逻辑必须写成“两个子序列都还有元素时才比较一方空了就直接拷贝另一方剩余部分”。顺序不能反否则轻则数据错乱重则数组越界。好的习惯是在 merge 函数的入口处加一个断言确认 left mid right并且传入的 temp 数组下标范围够用。面试时你说一句“我会在最开始做一个边界检查”面试官对你的印象分会好很多。4.3 递归层级太深怎么办如果待排序数组长度是 100 万递归深度是 log₂(100万) ≈ 20完全没压力。但如果你在 Java 里默认的递归栈不够或者你处理的是链表结构而链表的递归实现又每家写法不同可能在 10 万级数据时就开始出问题。我自己的经验是真正工作里归并排序处理几十万数据都不会栈溢出真正害怕栈溢出的是快速排序这种可能退化的递归。如果你实在担心可以把归并排序改成自底向上的迭代版本。自底向上的归并排序思路也不难先合并长度为 1 的相邻段得到长度为 2 的有序段再合并长度为 2 的相邻段得到长度为 4 的有序段以此类推。迭代版本不需要递归也就不存在栈溢出问题。代码如下void mergeSortIterative(vectorint arr) { int n arr.size(); vectorint temp(n); for (int width 1; width n; width * 2) { for (int left 0; left n - 1; left 2 * width) { int mid min(left width - 1, n - 1); int right min(left 2 * width - 1, n - 1); // 复用之前定义的 merge 函数 merge(arr, left, mid, right, temp); } } }注意width * 2可能会溢出要是 n 很大建议写成width min(width * 2, n)或者干脆用 long 类型。这个细节一般不致命但严谨一点没坏处。4.4 性能实测递归和迭代哪个快我在自己机器上对一个 100 万随机整数的数组做了测试递归版本比迭代版本快了大约 10%。原因可能是递归版本天然有更好的局部性每一层对内存的访问模式更贴近 CPU 缓存而迭代版本外层循环跳跃范围较大缓存命中率略差。但这一点在不同语言、不同编译器下差异很大我建议你在自己的环境里实测别盲目相信网上的结论。工程上如果数据规模上亿我会利用并行流或者多线程对左右子数组分别排序再合并这样能进一步压榨多核性能。5. 归并排序的高频变体与应用场景归并排序本身是一个完整的算法但它之所以能在算法面试和工程中占据一席之地很大一部分原因是它衍生出的几个变体直接映射了现实问题。我挑三个最高频的展开。5.1 求逆序对数量逆序对指的是数组中满足 i j 且 arr[i] arr[j] 的两元组(i, j)。暴力求解是 O(n²)但如果用归并排序可以在合并过程中顺带统计逆序对数量总时间依然是 O(n log n)。核心洞察是合并两个有序子序列时如果右半部分的某个元素 arr[j] 比左半部分的 arr[i] 小那么左半部分从 i 到 mid 的所有元素都大于 arr[j]这些都能和 arr[j] 形成逆序对。因此在 merge 中发现arr[i] arr[j]时把mid - i 1累加到答案里即可。这个题的变体在各大厂笔试里反复出现因为它考察的不只是会不会背归并排序而是能不能理解归并过程中“比较次序”背后的信息量。我个人建议你把逆序对统计的代码亲手写一遍比单纯看十遍都管用。5.2 链表的 O(n log n) 排序数组排序随便写但链表排序就不一样了。因为链表不支持随机访问很多依赖下标的排序算法快排、堆排很难直接实现而归并排序对链表的适应性极好——你只需要找到中点快慢指针递归排序两段然后做链表的合并。合并不需要额外空间只需要修改 next 指针。实现时有两个细节。第一找中点用快慢指针快指针每次走两步、慢指针每次走一步快指针到末尾时慢指针正好在中点。第二在递归时记得把两个子链表断开否则合并时可能无限循环。链表归并排序的时间复杂度依旧是 O(n log n)空间复杂度因为递归栈是 O(log n)比数组版更省内存。这是 LeetCode 148 题的标准解法值得背下来。5.3 外部排序当内存装不下数据时如果你要排序一个 100 GB 的文件但内存只有 8 GB全部数据不可能一次载入。这时候就是外部排序登场。经典策略就是归并排序思想的延伸把大文件分块读入内存每块比如 1 GB用普通快排排好写回磁盘。这样得到 100 个有序的小文件分块。从每个分块文件里读入一段数据到内存缓冲区做多路归并不断从缓冲区中选出最小值写入输出文件哪个缓冲区空了就从对应分块继续读。最终合并成一个整体有序的大文件。实际系统的多路归并会用败者树来优化多路选择最小值的效率。但核心思想仍然是“分解-解决-合并”。所以说归并排序是算法课里“学完立刻能用到生产环境”的少数排序算法之一完全不是纸上谈兵。5.4 混合排序Timsort 的启发Java 的 Arrays.sort() 在对对象数组排序时用的是 Timsort一种改良版归并排序它的思想是对于接近有序的序列先用二分插入排序把连续的自然有序片段识别出来然后再用归并操作把它们合并。这种“利用数据本身特点 分治合并”的思路让排序在真实数据上通常比理论最坏情况快得多。我在实际项目中处理一批已经部分有序的数据时也借鉴过这个思路先扫描出天然有序的片段然后只对这些片段做归并性能比单纯的快速排序稳定很多。这就是归并排序思想的生命力——它不是一个孤立的模板而是打开“通过组合数据特征和分治策略解决问题”这扇门的一把钥匙。6. 常见问题与避坑经验速查写归并排序的时候我踩过一些坑也看过很多学生踩坑。这里整理一份清单按“症状-原因-对策”的方式列出希望对你有帮助。症状原因对策结果只是部分有序合并时没比较完直接拷贝全部检查 while 循环条件一方为空后追加剩余部分递归一直不结束导致栈溢出递归边界时区间没缩小检查 mid 计算和递归参数使用闭区间约定合并后原数组没变修改的是临时数组忘了拷贝回来merge 末尾一定要把 temp 区间拷贝回原数组大数组排序很慢每次递归现建临时数组改为外部一次性申请 temp递归时通过下标复用数组值重复时顺序乱掉合并条件写成了而不是相等时必须让左半部分先放入保证稳定性整型溢出导致中点算错left right 溢出mid left (right - left) / 2还有一个容易被忽略的调试技巧排序算法写完不要直接拿大规模数据测试。先写一个暴力排序比如 Python 的 sorted然后用随机数生成器生成小数组长度 5~20把归并排序结果和暴力排序结果对比不同就打印出输入数组。这样能在几秒钟内定位 bug而不用对着 10 万条调试日志崩溃。这个习惯我一直保留到现在工作里写任何自定义排序逻辑都这么验证效率奇高。另一个实战经验如果你在写归并排序的泛型版本比如 Java 的 Comparator 版本相等元素的处理一定要用否则破坏了稳定性。有人觉得稳定排序无所谓但在真实系统里两个字段连续排序的场景太常见了稳定性直接决定二次排序结果是否正确。7. 从归并排序到分治思维的方法论最后我想聊点学习层面的东西。合并排序本身不难但真正难的是把“分治”这两个字内化成你解决问题的本能。我自己的心得体会是在遇到一个复杂度看起来是 O(n²) 的问题时先别急着优化常数停下来想想三件事第一这个问题能不能拆成两个独立的子问题如果能子问题之间是不是没有重叠没有重叠才有资格用分治如果子问题之间重叠很多比如斐波那契数列的朴素递归那更适合动态规划而不是分治。第二拆完之后合并的代价能不能做到线性或接近线性归并排序成功的前提是合并是 O(n)如果合并本身要 O(n²)那你整个算法还是 O(n² log n) 甚至更糟。分治不是万能的关键在合并成本。第三递归的深度有多大如果每次规模缩减不是固定比例的常数递归树可能会退化成链那样分治就失去了意义。这也是为什么我们设计分治算法时要保证“平衡”分解。学习《算法导论》这一章时我强烈建议不要只盯着归并排序的代码。把书里的“递归式求解”和“主定理”也一并吃透这是理解很多后续高级算法如分治FFT、CDQ分治、整体二分的基础。你越往后学越会发现合并排序只是一个引子分治思想会像杠杆一样放大你的解题能力。如果你是从零开始学算法的读者我的建议是先手写一个无 bug 的递归归并排序数组版再手写一个无 bug 的链表归并排序再做一道逆序对统计题最后打开主定理那一节对着例 4 自己推一遍 T(n) 2T(n/2) n 的展开过程。这一套流程走完你对分治法的理解就不会只是“背模板”而是真正有了肌肉记忆。归并排序是我在面试里最常让候选人手写的一个算法。不是因为它是最高级的排序而是因为从代码风格、边界处理、临时数组的使用到对复杂度的口头推导能一气呵成讲明白的人通常对算法基础都掌握得很扎实。希望这篇东西能帮你也成为那个“一气呵成”的人。