1. 归并排序到底在做什么分治思想与执行流程归并排序是被讨论最多但也是最容易被轻视的经典排序之一。它的平均时间复杂度稳定在 O(nlog2n)无论输入是刚好乱序还是接近有序这个上界都不会变。很多人能背出递归代码却说不清为什么需要临时数组、为什么先递归再合并、为什么合并过程一定要双指针。这篇文章想把归并排序从思想层到代码层彻底拆开先讲它到底在做什么再推导 O(nlog2n) 的来源然后给出可直接复用的递归版和迭代版实现最后聊工程落地时真正值得注意的坑和优化。适合读这篇内容的人有两类一类是准备技术面试的开发者归并排序几乎是必考点而且经常衍生出逆序对、链表排序、外部排序等问题另一类是工作中要写数据处理工具的工程师需要在大数据量排序时选对算法。文章里的代码我以 Python 为主但思路可以平移到任何语言。1.1 分治思想拆解不是“把一个数组拆开”这么简单分治策略有三个动作分解、解决、合并。归并排序对这三个动作的执行顺序非常明确先递归地把数组分成两半直到每个子数组只剩一个元素然后开始逐步合并合并过程中完成排序。这里很多人有一个误区以为归并排序的核心是“拆分”。其实拆分只是辅助手段真正的排序发生在合并阶段。把一个数组拆到只剩一个元素时每个子数组天然有序因为单个元素不需要比较。接下来要做的就是把两个已经各自有序的数组按照大小关系合并成一个新的有序数组。这种“把无序数组变成若干有序片段再通过有序片段合并得到整体有序”的思路才是归并排序区别于冒泡、选择这些暴力排序的本质。另一个容易混淆的点归并排序和快速排序都用了分治但方向是相反的。快排是在分区之后就对数据做了调整使得基准值左边的数据都小于等于它、右边的数据都大于等于它然后递归处理左右两边而归并排序先递归到底排序实际发生在“归”回来的路上。这也是为什么归并排序在合并时需要辅助空间而快排可以在原数组上通过交换完成分区。1.2 合并两个有序数组整个算法的灵魂假设你有两个已经排好序的数组比如 [1, 3, 5] 和 [2, 4, 6]要把它们合并成一个有序数组最自然的做法是双指针一个指针指向左数组开头一个指针指向右数组开头每次比较两个指针指向的元素较小的放入结果数组然后对应指针后移。如果某一方先走完就把另一方的剩余元素直接接到结果后面。这个过程看起来简单但它决定了归并排序的稳定性。如果我们比较的时候使用arr[i] arr[j]而不是那么两个相等的元素会优先取左边的这样在合并过程中不会破坏相同元素的原始相对顺序。稳定性在业务场景里非常关键比如先按时间排序、再按优先级排序如果第二次排序是不稳定的第一次排序的顺序就白做了。合并两个有序数组的操作就是 merge。整个归并排序的执行过程可以理解成无数个 merge 嵌套在一起最小规模是两个长度为 1 的数组合并成长度为 2 的有序数组然后两个长度为 2 的数组合并成长度为 4 的有序数组一层一层向上直到最后两个长度为 n/2 的数组被合并成完整的 n 长度数组。1.3 手动模拟一趟完整合并建立递归直觉用经典的数组 [38, 27, 43, 3, 9, 82, 10] 走一遍。先按中点拆分成 [38, 27, 43, 3] 和 [9, 82, 10]左半部分继续拆成 [38, 27] 和 [43, 3]再拆成 [38]、[27]、[43]、[3]。从最底层开始合并[38] 和 [27] 合并成 [27, 38][43] 和 [3] 合并成 [3, 43]然后这两个有序数组再合并成 [3, 27, 38, 43]。另一边也做同样的事情[9, 82, 10] 拆成 [9]、[82]、[10]合并后得到 [9, 10, 82]。最后两个有序数组 [3, 27, 38, 43] 和 [9, 10, 82] 双指针合并得到 [3, 9, 10, 27, 38, 43, 82]排序完成。注意整个过程的执行顺序是深度优先的先一路拆到最左边的最底层完成合并再回来处理右边的分支。这也是递归程序的特点理解这一点后写代码时就不会纠结为什么合并函数要在两次递归调用之后才执行。2. O(nlog2n) 是怎么算出来的复杂度推导与直觉2.1 从递推公式到递归树假设输入规模为 n归并排序把问题拆成两个大小为 n/2 的子问题每个子问题的代价是 T(n/2)合并两个有序子数组需要扫描所有 n 个元素代价是 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 ... (2^k)T(n/2^k) k*n当递归到达底层时n/2^k 1也就是 k log2n。代入后得到 T(n) n*T(1) log2n * n O(nlog2n)。这个推导过程建议亲手写一遍。很多面试里问“归并排序为什么是 O(nlog2n)”本质上考的不是你能不能背出结论而是能不能从递推式出发解释层数和每层代价。递归树法和这个展开是等价的树的高度是 log2n每一层所有子问题加起来都要处理 n 个数据所以总代价是 n 乘以树高。2.2 层数为什么是 log2n一个生活化类比可以把归并排序想象成一个班级广播通知的下发过程一个老师告诉两位班长两位班长各自告诉四位组长四位组长再告诉八位组员。每次信息传递量翻倍从 1 到 n需要的层数就是从 n 除以 2 一直到 1 的除法次数也就是 log2n。归并排序的递归树高度正好是这样的对数结构。每层合并代价都是 O(n) 这一点也值得展开。第 0 层只有一次合并扫描 n 个元素第 1 层有两次合并每次扫描 n/2 个元素加总还是 n第 2 层有四次合并每次扫描 n/4 个元素加总依然是 n。无论哪一层所有合并操作的总扫描长度都是 n。这个规律贯穿整个算法所以复杂度就是“层数乘以每层代价”即 log2n 乘以 n。说到这里必须提醒一点O(nlog2n) 是平均时间复杂度同时也是最好和最坏时间复杂度。归并排序不会因为输入已经有序而减少比较次数也不会因为输入完全逆序而增加比较次数。这一点和插入排序形成鲜明对比插入排序的最好情况只有 O(n)。归并排序的这种确定性在实时性要求高的场景里是优势在追求极致性能的缓存场景里也可能成为劣势这点后续会展开。2.3 空间复杂度与稳定性为什么临时数组是刚需归并排序的空间复杂度是 O(n)因为每次合并两个有序数组时需要一个和整体规模等长的临时数组来存放结果。递归调用本身的栈深度是 log2n所以如果严格计算总空间占用是 O(n) 加上 O(log2n) 的函数栈但 O(log2n) 被 O(n) 主导通常就记作 O(n)。很多人会问能不能不用临时数组在原数组上直接完成归并如果严格要求原地也可以做但要么用复杂的原地旋转算法把时间复杂度推到 O(nlog2n) 上方要么牺牲排序稳定性工程上都不划算。一个更常见的做法是预先分配一个长度为 n 的临时数组在递归过程中反复使用它而不是每次 merge 都新建数组。这样空间开销只是 O(n)不会变成 O(nlog2n)。稳定性来源于合并时对相等元素的处理。如果写成if arr[i] arr[j]相等的时候先取左半部分那么原始顺序就被保留了。如果写成相等时先取右半部分稳定性就被破坏。很多初写归并排序的人在这里不小心写错导致排序结果正确但“稳定排序”的名头丢了。3. 递归版与迭代版完整实现代码是最快的说明书3.1 递归实现的正确姿势递归版归并排序的代码结构非常固定外层是排序函数内层是合并函数。一个容易踩的坑是临时数组的处理。不要在递归函数内部反复创建数组正确的做法是在入口函数里一次性创建好然后作为参数向下传递。def merge(arr, left, mid, 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 t in range(left, right 1): arr[t] temp[t] def merge_sort_recursive(arr, left, right, temp): if left right: return mid left (right - left) // 2 merge_sort_recursive(arr, left, mid, temp) merge_sort_recursive(arr, mid 1, right, temp) merge(arr, left, mid, right, temp) def merge_sort(arr): temp [0] * len(arr) merge_sort_recursive(arr, 0, len(arr) - 1, temp)注意两点mid left (right - left) // 2而不是(left right) // 2后者在极端情况下可能产生整数溢出虽然 Python 的整数不会溢出但其他语言需要养成这个习惯。另外合并结束后要把临时数组拷贝回原数组。这里用的是循环拷贝如果是在 Python 里也可以直接用切片arr[left:right1] temp[left:right1]但循环更便于理解也避免了切片带来的额外对象开销。3.2 自底向上的迭代实现递归实现的缺点是当数组规模特别大时递归深度会达到 log2n虽然不容易爆栈但在某些嵌入式环境或函数栈极小的环境里仍然不放心。迭代版自底向上实现完全避开递归方法是从合并长度为 1 的子数组开始循环处理长度为 2、4、8 直到整个数组。def merge_sort_iter(arr): n len(arr) if n 2: return arr temp [0] * n width 1 while width n: left 0 while left n: mid min(left width - 1, n - 1) right min(left 2 * width - 1, n - 1) if mid right: merge(arr, left, mid, right, temp) left 2 * width width * 2 return arr这里的 merge 函数和递归版共用。迭代版的核心是width每次翻倍left 每次前进2 * width保证当前合并的两个区间分别是 [left, mid] 和 [mid1, right]。当数组长度不是 2 的幂时需要借助min对 mid 和 right 做钳制。if mid right这个判断很重要如果不加当左区间已经包含数组剩余全部元素时合并会去访问一个不存在的右区间。3.3 两种写法在工程上如何取舍递归版更符合分治思想代码可读性好调试的时候可以用调用栈直观看到分解过程。迭代版代码稍显繁琐但避免了递归调用开销在数据规模极大时更稳。我个人的习惯是日常业务代码用递归版因为逻辑清楚、不易出错底层工具或需要极致稳定性的场景用迭代版。下表简单对比两种实现的差异维度递归版迭代版代码可读性高和思想一一对应低需要理解 width 和 left 的推进关系函数调用开销有但影响通常可忽略无递归纯循环栈空间压力需要 O(log2n) 递归栈几乎不需要额外栈边界处理难度较简单需要小心钳制 mid 和 right适用场景面试、业务排序、教学嵌入式环境、超大数组、无递归环境4. 工程落地避坑指南边界、内存与微优化4.1 最容易被忽略的边界条件归并排序写错的原因通常不是算法思想不对而是边界处理不到位。第一个高频错误是递归终止条件写成left right这本身也能工作但会多一层无意义的递归更规范的是left right。第二个高频错误是对mid的划分。假设数组下标是 [left, right]左区间应该是 [left, mid]右区间是 [mid1, right]。如果错误地把右区间写成 [mid, right]左区间会多一个元素最终排序结果虽然可能正确但会让两个区间不均衡破坏了归并排序的分治逻辑甚至可能导致死循环。而且 mid 的计算方式必须和迭代版的钳制逻辑一致否则左右区间会出现重叠或漏掉元素。第三个错误出现在合并后的拷贝阶段。有些人只把临时数组的一部分拷回原数组比如从 0 开始拷到 right-left却没有考虑 left 的偏移量。当 left 不是 0 时这种写法会污染原数组里不属于当前合并范围的元素。正确的做法是从 left 开始循环到 right把 temp 对应位置拷回去。4.2 临时数组分配策略统一分配还是每次创建很多初学版本的代码长这样在 merge 函数内部temp [0] * (right - left 1)看起来没错但每次递归调用都要重新分配数组整体空间分配次数等于合并次数约为 n 次量级。对于十万元素或许还能忍受对于百万千万级数据创建大量临时对象不仅耗时还容易触发内存碎片。工程上的标准做法是在入口函数里一次性分配temp [0] * n之后所有递归层级共用这一块空间。这是因为每次合并只需要访问当前区间对应的位置不同分支递归并不会同时使用 temp 数组所以不存在数据覆盖问题。这种方法把动态内存分配从 O(n) 次降低到常数次效果非常明显。4.3 三个值得做的微优化第一个优化是小区间切换插入排序。当待排序区间长度小于某个阈值常用 16 或 32时不再继续拆分和合并而是直接对小区间做插入排序。插入排序在规模小的时候常数因子远小于归并排序而且缓存友好。这个优化是很多工业级排序库的基础做法。def merge_sort_optimized(arr, left, right, temp): if right - left 16: insertion_sort(arr, left, right) return mid left (right - left) // 2 merge_sort_optimized(arr, left, mid, temp) merge_sort_optimized(arr, mid 1, right, temp) if arr[mid] arr[mid 1]: return merge(arr, left, mid, right, temp)第二个优化是判断是否真的需要合并。如果左区间最后一个元素已经小于等于右区间第一个元素说明两个区间已经天然有序整段不需要做任何操作。这个判断只需要 O(1) 时间却能在处理近似有序数组时跳过大量合并直接把最好情况的时间复杂度从 O(nlog2n) 降到 O(n)。它和插入排序的近似有序友好特性殊途同归。第三个优化是减少元素的重复拷贝。标准写法每次合并完都把 temp 拷回 arr下一层合并又把 arr 拷到 temp。如果交替使用 arr 和 temp 作为目标数组可以让数据在两层之间直接往返省掉一部分拷贝。实现起来要复杂一些性能提升通常在 10% 到 20% 之间适合对性能有极致要求的读者自己去研究业务场景不一定需要。4.4 常见错误与排查思路如果排序结果只是部分有序先检查合并后拷贝的区间是否完整。如果数组完全没排序检查递归调用时 mid 的左右区间是否写反。如果出现越界异常检查 while 循环的终止条件是否写成i mid而不是i mid。这些错误在调试时不一定要看完整数组可以用小规模随机数组反复跑再对比 Python 内置的sorted()结果很快能定位。另一个实用技巧是在合并函数入口加一个断言assert left mid right确保调用 merge 时区间参数合法。很多问题不是算法问题而是调用方没有正确传入区间范围。加断言后测试阶段就能暴露问题而不是等线上数据出错。5. 归并排序的经典变体与应用场景5.1 逆序对统计merge 时的天然能力逆序对定义是如果 i j 且 arr[i] arr[j]这一对元素就是一个逆序对。暴力解法双重循环需要 O(n²) 时间而归并排序可以在合并过程中顺手统计时间复杂度降到 O(nlog2n)。原理其实很巧妙。合并两个有序子数组时当右区间的当前元素arr[j]小于左区间的当前元素arr[i]说明从 i 到 mid 的所有元素都大于arr[j]它们每一个都和arr[j]构成逆序对。此时一次性累加mid - i 1个逆序对而不是一个个比较。def merge_count(arr, left, mid, right, temp): i, j, k left, mid 1, left inv 0 while i mid and j right: if arr[i] arr[j]: temp[k] arr[i] i 1 else: temp[k] arr[j] j 1 inv mid - i 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 t in range(left, right 1): arr[t] temp[t] return inv这个写法注意一点只有arr[i] arr[j]时才计数等于的情况不计。因为等于不是逆序对用取左区间元素可以保证稳定性也不会多算逆序对。面试中经常把它作为归并排序的进阶题理解了这一行计数逻辑就掌握了一套高频解题思路。5.2 外部排序与多路归并如果数据量远超内存比如几十 GB 的日志文件要在内存只有几个 GB 的机器上排序普通快排或者归并都不能一次性完成。这时会用到外部排序而外部排序的核心就是把归并排序的思路放大到文件级别。基本流程是把大文件切分成多个可读入内存的块每块读入内存后用快排或归并排好序写回磁盘形成多个临时有序文件最后对这些有序文件做多路归并。多路归并不能简单两个文件两两合并因为那样会产生大量磁盘 IO工程上一般用优先队列维护 k 个文件的最小元素每次取最小写回输出文件同时从对应文件补一个元素进来。这个过程本质上是 k 路归并。之所以还是叫“归并”是因为它和内存归并排序共享同一个核心操作合并多个有序序列。区别只在于数据载体是文件以及为了减少磁盘 IO 引入的缓冲区设计。可以说如果不理解归并排序外部排序就很难展开这也是为什么很多大数据工程师会回头补排序算法的底层知识。5.3 链表排序归并排序的真正主场数组排序时归并排序需要 O(n) 额外空间这是它对比快排的最大劣势。但如果是链表排序归并排序不需要额外开辟存储空间因为链表节点之间的指针可以在合并时重新连接不需要新的节点数组。额外开销只有递归函数栈 O(log2n)这比数组归并要好得多。链表归并的核心思路用快慢指针找到链表中点切成左右两条链表递归排序后再用双指针合并两条有序链表。找中点的代码我经常看到有人写错def merge_sort_list(head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next right_head merge_sort_list(slow.next) slow.next None left_head merge_sort_list(head) return merge_two_lists(left_head, right_head)这里 fast 从head.next开始走可以让 slow 恰好停在左半部分的最后一个节点。如果 fast 也从 head 开始slow 可能会停在偏右的位置拆分就不准了。合并两条有序链表的函数则是典型的双哨兵节点技巧这里不再展开。5.4 与主流排序库的关系很多人以为归并排序只是教科书内容现实中都用内置排序。其实很多现代编程语言内置排序正是归并排序的改良版本。比如某些语言标准库里的排序算法是 TimSort它的核心思想是找到数组中已经有序的“run”然后用归并的方式把这些 run 合并起来同时在小规模时切换到插入排序。可以说 TimSort 就是“归并排序 插入排序 自然有序检测”的混合体。理解归并排序的价值不只是为了面试。当你遇到一个近似有序的大数组时原生快排可能表现平庸而基于归并思想的 TimSort 却能在 O(n) 时间完成排序。当你需要统计逆序对时归并排序是标准答案。当你处理链表时归并排序又是空间效率最高的稳定排序。这也是为什么它作为“经典排序”的地位一直没有被替代。6. 怎么选归并排序 vs 快排 vs 堆排的实战对比6.1 不同数据形态下的表现差异我用一组相对可控的实验数据说明一下感受。以下耗时不是精确基准值但比例能反映算法差异环境是一台普通开发机语言是 Python数据规模从十万到一千万。数据形态归并排序快速排序堆排序10 万随机整数约 0.04 秒约 0.03 秒约 0.06 秒100 万随机整数约 0.5 秒约 0.35 秒约 1.1 秒100 万近似有序约 0.08 秒带跳过优化约 0.05 秒pivot 选择好时约 1.0 秒100 万大量重复值约 0.4 秒约 0.3 秒约 1.2 秒1000 万随机整数约 7 秒内存占用显著约 5 秒约 15 秒从这张表可以看出几个规律归并排序在任何数据形态下都比较稳定但常数因子不是最小的快排在重复值和随机数上通常最快但遇到特定退化的 pivot 选择可能变慢且不稳定堆排序常数最大它的优势主要在内存占用固定、无递归以及优先级队列场景而不是单纯排序。6.2 工程选型的判断清单如果你的需求里包含下面任意一条优先考虑归并排序第一要求排序稳定相同元素顺序不能变第二数据源是链表结构第三数据量超过内存需要外部排序第四需要顺便统计逆序对第五实时系统希望排序耗时尽量可预测不管输入是否有序。如果你内存非常紧张比如单片机环境归并排序 O(n) 的辅助空间可能不可接受。此时要么选堆排序用 O(1) 空间换一个不那么快的排序时间要么选快排的原地分区版本。如果数据结构是数组、内存充足而且只关注速度快排往往更好。如果排序目标是基础类型且不需要稳定很多语言的原生双轴快排已经优化得很好也不一定要自己写归并。6.3 一点个人体会我从第一次写归并排序到现在最大的感受是它的思想价值大于代码价值。递归拆分让我们学会用对数视角看待问题合并过程让我们理解稳定性从何而来复杂度推导让我们知道层数和每层代价这两个维度构成了算法分析的基本框架。这些能力可以直接迁移到很多非排序问题上。如果你正在准备面试不要只背代码试着在白板上推导一遍 T(n) 2T(n/2) O(n)再手动模拟一个长度为 7 的数组的业务流程然后把递归版改成迭代版最后自己加上逆序对计数。这一套走完归并排序才算真正吃透了。工作中如果你碰到一个要求稳定排序的大数据场景或者需要把多个有序文件合并成一个你会感谢现在花时间把这些细节弄明白的自己。