归并排序：分治思想、代码实现与复杂度优化全解析-北京尧图网络

如果只能选一种排序算法来理解分治思想我的答案始终是归并排序。它不像快速排序那样依赖划分的运气也不像堆排序那样需要先接受一个难懂的数据结构核心思路一句话就能讲清把数组从中间切成两半两半分别排好序再合并成一条完整有序序列。真正动手实现的时候你会发现这句话背后藏着不少值得较真的细节边界条件怎么写、临时数组怎么开、稳定性靠什么保住、递归和迭代哪个更稳这些坑我都踩过。这篇就把归并排序从原理到代码、从优化到延伸整体讲透适合刚学算法的同学建立体系也适合工作几年后想回头补基础的人。1. 先搞清楚归并排序到底解决的是什么问题1.1 合并两个有序数组是一切的基础归并排序这个名字核心在归并两个字。归并的意思是给你两条已经排好序的序列把它们合并成一条仍然有序的序列。这事做起来非常直观可以想象手里有两副各自排好的牌每次比较两堆牌最上面那一张把点数小的那张先放进新牌堆里直到某一堆空了再把另一堆剩下的牌一股脑倒进去。用数据说就是左边是[1, 3, 5]右边是[2, 4, 6]。拿两个指针分别指向两边的开头1和2比1小取1再比3和2取2再比3和4取3……这样一轮下来新序列就是[1, 2, 3, 4, 5, 6]。这个操作的时间是线性的两个数组总长度为 n那么最坏情况也就是把每个元素都拿出来比较一次放一次O(n) 搞定。归并排序的全部秘密就是把这个简单的合并操作套进一个精巧的递归框架里。1.2 分治把大排序拆成小排序再拼回去如果直接让你排一个长度为十万的乱序数组脑子是蒙的。但如果是排一个长度为 1 的数组呢只有一个元素天然有序什么都不用做。长度为 2 呢比较一下交换一下完事。分治思想的妙处就在这把大问题拆成两个小问题小问题再拆成更小的问题直到拆到只有一个元素这种不用排就排好的程度然后再用合并操作一层层把小结果拼回大结果。以[4, 2, 5, 1]为例。先从中间切一刀得到左半[4, 2]和右半[5, 1]。左半继续切得到[4]和[2]各自有序合并成[2, 4]右半同理得到[1, 5]。最后把[2, 4]和[1, 5]合并成[1, 2, 4, 5]。看见没有排序本身我们其实没做几次正经排序绝大多数工作都是在做合并。这也是归并排序学起来最省力的地方你只需要理解两件事怎么把一个数组递归地切成小段怎么把两个有序小段合并成一个大段。切分逻辑极其机械合并逻辑又是线性的两者一组合就有了整个算法。2. 归并排序的核心原理分解、递归、合并这条主线2.1 一趟归并具体做了什么先看最底层的合并函数。假设要对数组 arr 中[left, mid]和[mid1, right]两段进行合并操作过程是把这两段分别拷贝到两个临时数组 L 和 R。用 i 指向 L 的开头j 指向 R 的开头k 指向 arr 中 left 的位置。反复比较 L[i] 和 R[j]谁小就写入 arr[k]然后对应指针前进一位。某一方的元素取完了把另一方剩余的元素全部顺次写入。举个例子合并[3, 7]和[1, 4, 5]。第一轮比3和1取1第二轮比3和4取3第三轮比7和4取4第四轮比7和5取5此时右半耗尽把左半剩下的7直接接上。最终结果是[1, 3, 4, 5, 7]。注意这里的稳定条件当L[i]等于R[j]时要写成也就是优先取左边数组里的元素。这个细节直接决定了归并排序是不是稳定排序后面我会专门展开讲。2.2 自上而下的递归切分递归版本是归并排序最经典的形态。它的逻辑可以描述为对一个区间[left, right]如果left right说明区间里只有一个元素或为空直接返回否则算出中点 mid先递归排序左半再递归排序右半最后把两个有序段合并。从宏观上看整个递归过程形成一棵二叉树。以 8 个元素为例第一层分成两个长度为 4 的子问题第二层分成四个长度为 2 的子问题第三层是八个长度为 1 的子问题。这棵树的深度是 log2(8) 3每一层所有子问题加起来处理的元素总量都是 n 个所以总工作量就是 n 乘以树高也就是 O(n log n)。这里有个容易理解偏的点递归的顺序是先左后右但每层的合并时机是被递归天然安排好的。任何一层都不会在它的左右子问题还没排好序时就去合并所以合并操作拿到的永远是两条有序序列。2.3 自底向上的迭代归并递归是从大往小拆迭代则是反着来从小往大合。一开始把数组想象成一个个长度为 1 的有序段相邻两段两两合并成长度为 2 的有序段然后长度为 2 的相邻段两两合并成长度为 4 的有序段以此类推段长翻倍直到整条数组只剩一个段。用[6, 2, 5, 3, 1, 4]走一遍第一次段长 1合并[6]和[2]得到[2, 6]合并[5]和[3]得到[3, 5]合并[1]和[4]得到[1, 4]数组变成[2, 6, 3, 5, 1, 4]。第二次段长 2合并[2, 6]和[3, 5]得到[2, 3, 5, 6]剩下的[1, 4]单独成段。第三次段长 4合并[2, 3, 5, 6]和[1, 4]得到[1, 2, 3, 4, 5, 6]。这段过程没有递归只有循环好处是不用担心递归深度坏处是要小心处理数组长度不是 2 的整数次幂时最后那个落单的段。实战里这两种写法都很常见递归版好理解迭代版适合对栈深度敏感的场景。3. 两种实现方式的完整代码与边界走查3.1 递归版实现直接用 Python 写一版最朴素的递归归并关键逻辑都保留在合并函数里def merge(arr, left, mid, right): # 把左右两段分别拷贝出来 L arr[left:mid1] R arr[mid1:right1] i j 0 k left # 谁小取谁相等时取左边保证稳定性 while i len(L) and j len(R): if L[i] R[j]: arr[k] L[i] i 1 else: arr[k] R[j] j 1 k 1 # 把剩余部分直接接上 while i len(L): arr[k] L[i] i 1 k 1 while j len(R): arr[k] R[j] j 1 k 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)调用时写merge_sort(arr, 0, len(arr) - 1)就行。这段代码用来学习非常清楚但仔细看会发现一个性能隐患每次 merge 都做切片操作等于每一层递归都要重新分配内存。后面我专门有一节讲怎么避免这个问题。3.2 迭代版实现迭代版不递归用宽度变量控制归并粒度def merge_sort_iterative(arr): n len(arr) 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, left, mid, right) width * 2拿长度 6 的数组验证一下width1 时left 依次为 0、2、4对应的 right 分别是 1、3、5都满足mid right所以三组都合并。width2 时left 为 0、4第一组的 mid1、right3合并第二组 mid4、right5但是 leftwidth-1 4 n-1 5? 不对这里 mid min(02-1, 5) 1? 让我重新算left4, width2, mid min(42-1, 5) 5, right min(44-1, 5) 5mid right不合并正确。width4 时left0mid3right5合并成完整有序数组。这个版本的边界设计最值得玩味mid 和 right 都用了min去截断避免访问越界if mid right又保证不会对单个落单段做无意义的合并。理解了这两个保护条件迭代版就没什么秘密了。3.3 为什么这些边界条件必须这样写我在带别人写归并排序时发现十个新手有八个错在边界上集中在三个地方。第一个是递归出口。if left right而不是if left right。虽然理论上 left 不会超过 right但防御性写法能避免某些异常输入下的死循环而且语义更清晰地表达了空区间或单元素区间都直接返回。第二个是中点计算。(left right) // 2在数组特别大时可能溢出。比如某些语言里 left 和 right 都是很大的 int加起来的和超过整型上限就会出问题。更稳妥的写法是left (right - left) // 2。Python 里整数不会溢出所以没这个烦恼但如果你用 C 或 Java请养成第二种写法的习惯。第三个是合并结束后处理残余元素。很多初学者写完主 while 就以为完事了结果数组尾部多出几个永远没写回的元素。两个残余 while 循环缺一不可因为只要有一方的元素先取完另一方剩下的元素必须原样补上。另外迭代版本里if mid right这个判断是精髓。数组长度不是 2 的幂时最后一轮经常出现有左段没右段的情况这时候不做合并并不丢数据因为左段在上一步已经是有序的了它只需要保持现状参与下一轮或成为最终结果。4. 复杂度与稳定性的几个反直觉结论4.1 O(n log n) 的时间复杂度怎么来的归并排序的时间复杂度递推式是 T(n) 2T(n/2) O(n)。意思是规模为 n 的问题拆成两个规模为 n/2 的子问题每个子问题完成后还要做一次 O(n) 的合并。展开递推T(n) 2T(n/2) n 4T(n/4) 2n ... nT(1) n log2 n所以总复杂度是 O(n log n)。这里真正反直觉的点在于归并排序的最好、最坏、平均时间复杂度全是 O(n log n)。快速排序最怕已经有序的输入会退化到 O(n²)堆排序虽然也是 O(n log n) 稳定但常数因子大。归并排序则完全无视输入顺序无论数据是升序、降序还是完全随机递归树长得一模一样工作量也一模一样。这个特性在需要处理顺序不确定的数据时是个巨大的优点。不过要坦诚说一句算法题里 O(n log n) 是一个量级工程里常数因子同样重要。归并排序因为要搬移数据常数不算小所以它不见得是纯内存排序的最优选择但它的复杂度上界是铁打的这一点谁都不能反驳。4.2 空间复杂度 O(n)归并排序最常被吐槽的点归并排序不是原地排序。合并两个有序数组时需要一个和原数组规模相当的临时空间来存放数据。最朴素的实现里每次 merge 都要拷贝左右两段单次合并的临时空间是 O(段长)但递归过程中同一时刻最多有 O(n) 的空间被占用所以总空间复杂度是 O(n)。很多人误以为迭代版能省掉这个空间其实省不掉。迭代版只是省掉了递归栈的 O(log n)合并本身需要的 O(n) 临时数组一分不少。真正能做到严格原地归并的算法是存在的但实现极其复杂常数因子大得离谱一般不会在实战中用。如果面试官问你归并排序的空间复杂度为什么是 O(n)你要能答出因为合并操作需要一处能够容纳整个区间数据的暂存区无论递归还是迭代这个暂存区都省不掉。顺带一提递归本身还会额外消耗 O(log n) 的栈空间。对于深度递归比如处理数百万元素时某些语言会把栈爆掉这时候就该考虑我给的迭代版本。4.3 稳定性什么时候它是决定性的排序算法的稳定性是指两个值相等的元素排序后相对顺序不变。归并排序天然稳定因为合并时写着L[i] R[j]相等时先取左边左边来自原数组靠前的段于是相等元素的先后顺序被原样保留。为什么稳定这么重要因为现实中排序很少只按一个字段排。比如一个对象数组既有时间字段又有优先级字段你想先按时间排时间相同再按优先级排。稳妥的做法是先按优先级排一遍再按时间排一遍第二遍排序如果稳定第一遍的优先级顺序就会被保留。选择排序、堆排序、以及经典的快排分区方案都不稳定遇到这类多关键字排序需求时归并排序和插入排序、冒泡排序一样是稳定阵营里的主力。算法平均时间最坏时间额外空间稳定性冒泡排序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(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定这张表值得存一下。选排序算法时先看稳定性需求再看空间约束最后看常数因子绝大多数工程决策都是在这三者的权衡中做出来的。5. 实战优化技巧与踩坑记录5.1 临时数组复用别在递归里反复开内存我最早自己写归并排序时用的就是切片版本代码看着干净跑起来性能一言难尽。问题在于切片本质是拷贝每一层递归几十上百次 merge每次都要重新创建列表分配和垃圾回收的开销把 O(n log n) 的优势全抵消了。更好的做法是全程只申请一次和原数组等长的辅助数组 auxmerge 时先把当前区间拷贝到 aux再从 aux 归并回 arr。这样内存分配从每层每次变成整个排序一次性能提升非常明显。核心合并可以写成def merge_with_aux(arr, aux, left, mid, right): # 拷贝当前区间到辅助数组 for k in range(left, right 1): aux[k] arr[k] i, j left, mid 1 for k in range(left, right 1): if i mid: arr[k] aux[j] j 1 elif j right: arr[k] aux[i] i 1 elif aux[i] aux[j]: arr[k] aux[i] i 1 else: arr[k] aux[j] j 1这个写法省掉了单独的残余元素循环把四路分支统一进一个 for 循环属于我比较推荐的经典形式。递归函数里把 aux 作为参数一路传下去就能保证全程只有一个临时数组。5.2 小数组切换插入排序归并排序的递归到底层时频繁的函数调用占比会越来越高。处理长度为 1 的一段也要走一次完整的 merge_sort 调用链这个开销对性能影响不小。工业级的归并排序实现几乎都会加一个阈值判断当区间长度小于某个阈值时直接改用插入排序。原因很朴素插入排序在小规模数据上常数极小而且对几乎有序的数据特别快。阈值取 15 到 30 之间比较常见我习惯取 16。实际测试中这个优化对随机数据大概能带来 10% 到 20% 的加速对近乎有序的数据收益更大。实现时只需要在 merge_sort 开头加一行if right - left 1 THRESHOLD: insertion_sort(arr, left, right) return很多语言内置排序的混合策略也是这个思路先用插入排序把数组切成若干个小有序块再用归并思想把它们叠起来。5.3 归并的提前结束与哨兵技巧还有两个小技巧值得掌握。第一个是已有序提前结束merge 之前看一眼如果arr[mid] arr[mid1]说明左半最后一个元素已经不大于右半第一个元素两个区间拼在一起根本不需要做任何合并。这个检查对近乎有序的数据作用极大等于天然适配了数据已经排好的场景。第二个是哨兵。在左段和右段末尾各放一个足够大的无穷大值这样合并时永远不会出现一方先取空的情况主循环就不用写越界判断。经典算法书里经常用这种写法逻辑很优雅。但要注意哨兵值必须比数据里所有值都大如果数据是泛型或者包含浮点数使用float(inf)可能引发比较异常。我的建议是刷题和教学可以用哨兵工程里还是用我第一段给出的四路分支版更稳妥少一点花活少一点坑。5.4 链表版的归并排序省掉额外空间归并排序有个数组版本实现不了的隐藏优势它特别适合链表。因为链表不支持随机访问快速排序的 partition 操作需要反复遍历效率很差而归并排序的核心操作是按顺序访问元素链表完全能胜任而且合并链表时只需要改指针不需要临时数组。链表的归并排序同样分两步第一步用快慢指针找到链表的中点把链表拆成两半第二步递归排序两半第三步把两个有序链表合并。合并两个有序链表的代码比数组版更清爽用个哑节点存结果def merge_two_lists(a, b): dummy Node(0) tail dummy while a and b: if a.val b.val: tail.next a a a.next else: tail.next b b b.next tail tail.next tail.next a if a else b return dummy.next链表变化多写的时候特别容易在指针衔接上出错我的经验是每步操作后立刻检查tail是否已经移动到新链表的末尾不然很容易把链子接断。面试里碰到对链表排序的题归并排序基本是标准答案。6. 归并排序的延伸外部排序、逆序对与混合排序6.1 外部排序把归并思想搬到内存之外归并排序能从一个教科书算法变成工程利器的分水岭在于外部排序。假设你有一个 100GB 的日志文件要排序而内存只有 2GB这时候所有需要整体载入内存的排序算法全部失效归并排序却是唯一能优雅存活的那一个。外部排序的两阶段是这么做的。第一阶段把大文件切成若干个能塞进内存的小块每块在内存里用常规排序排好写回磁盘形成一批有序小段术语叫 run。第二阶段不断从各个有序段中取出最小的元素归并成更大的段。多路归并时一般用一个最小堆来选出当前所有段头里最小的那个每写入一个元素就从对应段补充下一个堆里始终保存每段当前的头部元素。排序 100GB 文件需要几趟归并取决于内存能同时容纳多少路输入。如果内存能同时开 k 路归并一趟就能把段数量缩小到原来的 1/k。外部排序的代价主要在磁盘读写上所以优化方向都指向减少 I/O 次数和顺序读写的效率上。这个场景下归并排序的多路和稳定两个特性变得无比金贵。6.2 逆序对统计归并排序的隐藏技能归并排序在合并阶段本来就一直在比较元素之间的大小关系稍微改造一下就能顺手统计逆序对数量。所谓逆序对就是数组中满足 i j 且 a[i] a[j] 的配对比如[3, 1, 2]里有(3,1)和(3,2)两对。关键观察在合并阶段当右段的R[j]小于左段当前的L[i]时说明L[i]以及它后面还没取出的所有左段元素统统都比R[j]大它们与R[j]都会构成逆序对。所以此时直接给计数加上len(L) - i而不是加 1。这样一次归并就能统计出跨左右两段的所有逆序对整个排序过程正好覆盖所有可能的配对总复杂度维持 O(n log n)。def merge_and_count(arr, left, mid, right): L arr[left:mid1] R arr[mid1:right1] i j 0 k left count 0 while i len(L) and j len(R): if L[i] R[j]: arr[k] L[i] i 1 else: arr[k] R[j] j 1 count len(L) - i k 1 while i len(L): arr[k] L[i] i 1 k 1 while j len(R): arr[k] R[j] j 1 k 1 return count这个技法我强烈建议掌握它比用双层暴力循环验证两两配对要优雅太多而且能加深你对归并过程的直觉。6.3 混合排序策略为什么内置排序不直接叫归并很多现代语言的内置排序最终都没有采用纯归并排序的形态而是用了混合策略小数组用插入排序大数组尽量识别天然有序段再用归并思想把段叠起来。这样既保留了归并排序稳定和 O(n log n) 上界的优点又对真实世界部分有序的数据格外友好还把归并排序最让人不爽的大常数压了下去。Python 的内置排序就是对这类混合策略的一个实例。它自动检测已经有序的子段对几乎排好的数据能做到接近线性的表现同时保持稳定。所以日常开发里你基本不会手写归并排序去代替内置排序但归并的思想渗进了太多地方多路归并、日志合并、分治统计、外存数据处理处处都有它的影子。我自己在实际项目里最常用到归并思想的地方是合并多个上游接口返回的已排序列表。比如从几路分页接口拿到各自有序的数据要在内存里合成一个全局有序的结果集直接套 merge 的主循环比把所有数据堆到一起再全量排序快得多内存占用也小。每次做这种事我都会感慨归并排序的价值从来不只是那几行递归代码而是一种把零散有序数据重新组织成全局有序的能力。学会它你等于获得了一套处理有序数据流的通用方法论这比背下任何一段具体实现都更有意义。

归并排序：分治思想、代码实现与复杂度优化全解析

相关推荐

ProCAST中文帮助文档：铸造仿真参数速查与缩孔预测指南

32 层混合注意力架构拆解：Qwen3.5-9B_gpuep_1.0_gpu_128 如何用线性注意力撑起 256K 上下文

千元“双拆除”锐龙R7迷你主机：0.68L小钢炮能玩黑神话？

更多资讯

大模型生产级后训练：从微调到可落地的流水线

生产级后训练实战：从数据准备到模型部署的完整指南

Muse Code新计划解读：本地AI辅助编码与批量任务实践指南

AI应用工程化实践：从模型选型、本地部署到批量任务落地

VC++ 通过 USB 直连 GT800 打印 ZPL 标签：通道选型、指令拼装与避坑指南

WPE封包全套实战：从Winsock Hook到封包修改重放指南

今日更新

NetSpot 实战：用信道分析与频宽优化解决 Wi-Fi 卡顿

C++ split() 字符串分割的五种实现与性能实测

R语言坐标轴范围设置：从xlim/ylim到coord_cartesian的完整指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？