1. 从两摞牌说起归并排序究竟适合什么场景归并排序Merge Sort这个算法我最早是在一本数据结构教材里看到的当时觉得它不如快速排序“性感”——快排在原地交换、常数小、面试出现频率高归并却要额外开一块临时空间看起来像个“笨办法”。但真正写过几个线上项目、处理过千万级日志排序之后我的看法变了归并排序是少数几个行为可预测的排序算法时间复杂度稳定在 O(n log n)不存在快排那种极端情况下退化成 O(n²) 的尴尬而且它天然稳定、天然适合外存。这几个特性决定了它在很多工程场景里无可替代。这篇文章我打算把归并排序从头到尾讲透不只是一段能跑通的代码而是把“为什么这样设计”“每一步操作的意图是什么”“哪里最容易写错”“工程里怎么用它”都掰开揉碎了讲。适合刚学算法想搞懂分治思想的同学也适合工作几年后想回头补一补基础的开发者。文中给的 Python、Java、C 三份实现都是我在实际项目里反复用过的版本可以直接抄。先说归并排序解决的核心问题它把“排序一个乱序数组”这个看起来无从下手的任务拆成“排序两个半区”和“把两个有序数组合并成一个”这两件小事。拆到最小每个子问题只剩一个元素一个元素本身就是有序的问题消失了。剩下的全部工作量都落在“怎么把两段有序序列快速拼成一段”上面。这个思路叫分治归并排序是分治思想最干净的一个载体。我常用一个生活比喻来解释你桌上有两摞已经按大小排好的扑克牌要把它们合成一摞有序的。你只需要看两摞牌各自最上面那张谁小就把谁拿出来放到新摞上重复这个动作直到一摞空掉再把剩下那摞整个挪过来。整个过程你只需要比较“两张牌”不需要回头看已经放好的牌。这就是 merge 函数的全部逻辑简单到可以用一句话讲完但真正写代码时边界处理能让一半以上的人第一次写错。2. 分治骨架拆解归并排序的整体设计思路2.1 分治三步拆、治、合以及每一步真正在做什么分治这三个字听着玄落到归并排序上其实是三个非常具体的动作。第一步“拆”就是把当前区间从中间切成左右两半切的位置用mid lo (hi - lo) / 2。这里我特意写成lo (hi - lo) / 2而不是(lo hi) / 2原因是后者在 lo 和 hi 都接近整型上限时会发生溢出虽然日常业务里数组长度很难到那个量级但养成这个习惯没有坏处尤其是在 C 和 Java 里。第二步“治”就是对左右两个半区分别递归调用自己。注意这里递归的终止条件——区间里只剩一个元素或者干脆为空。很多人写归并排序时喜欢用“长度小于等于 1 就返回”来判断这没问题但如果你的实现是区间式传 lo 和 hi那判断条件应该写成hi - lo 2含义是区间内元素个数少于两个天然有序。第三步“合”也就是 merge。这一步是整个算法的灵魂也是性能瓶颈所在。它的任务是把[lo, mid)和[mid, hi)这两段各自有序的子数组合并成[lo, hi)上一段新的有序序列。合并过程中需要一个辅助数组来暂存结果因为直接在原数组上覆盖会破坏还没读到的数据。这个辅助数组的大小通常等于整个数组长度在递归开始前一次性分配好避免每次 merge 都重新申请内存——这是一个很常见但很容易被忽略的优化点我在早期写 Java 版本的归并排序时就因为每次 merge 都new int[]导致千万级数据下 GC 压力巨大跑得比预期慢了好几倍。分治的真正价值在于它把一个 O(n²) 的朴素问题转化成了 O(n log n)。拆分的次数是 log n 层每一层所有子问题加起来处理的数据总量是 n两层相乘就是 n log n。这个推导我下面会展开讲。2.2 递归树视角O(n log n) 是怎么推出来的要理解归并排序为什么是 O(n log n)最好的方式是在纸上画一棵递归树。假设数组长度 n 是 2 的幂第一层是完整的 n 个元素需要合并一次代价 n。第二层拆成两个 n/2 的区间各自合并一次两次合并加起来还是 n。第三层四个 n/4加起来依然是 n。这样的层数正好是 log₂n因为每往下一层数组规模就减半减到 1 需要 log₂n 次。所以总代价是n × log₂n也就是 O(n log n)。用数学递推式写就是T(n) 2T(n/2) O(n)用主定理也能得到同样结论。这里有一个细节值得注意无论输入数据是随机排列、正序还是逆序归并排序的递归树形状都一样层数也都是 log n所以最好情况和最坏情况都是 O(n log n)。这就是它“行为可预测”的来源也是为什么很多对延迟敏感的系统宁愿多花一点内存也要用它。空间复杂度方面主要开销是那个和原数组等长的辅助数组所以是 O(n)。递归调用栈的深度是 log n相比之下可以忽略。这里对比一下快速排序快排平均也是 O(n log n)但空间是 O(log n)最坏能到 O(n)且最坏时间会退化到 O(n²)。所以两者是典型的“用空间换稳定性”的取舍。2.3 和快排、堆排、插排放在一起比什么时候该选归并面试里经常被问“快排和归并的区别”标准答案往往只讲稳定性和空间其实真正做技术选型时需要考虑的维度更多。我整理了一张我平时自己用的对比表参数来自实际压测和标准库实现的公开资料算法平均时间最坏时间额外空间稳定性典型适用场景归并排序O(n log n)O(n log n)O(n)稳定外存排序、链表排序、要求稳定快速排序O(n log n)O(n²)O(log n)不稳定内存内通用排序、缓存友好堆排序O(n log n)O(n log n)O(1)不稳定空间受限、求 Top K插入排序O(n²)O(n²)O(1)稳定小数组、近乎有序的数据计数排序O(n k)O(n k)O(k)稳定值域小的整数从表里能看出一条清晰的取舍线如果你要的是稳定或者数据在链表上、在磁盘上归并是首选如果你追求极致的常数因子和缓存局部性快排更合适如果内存极其紧张堆排是唯一选择。实际工程里的std::stable_sort、Java 的Collections.sort对象版本、Python 的sortedTimsort归并和插入的混合体都是归并家族的实现。Python 之所以在排序上表现那么稳很大程度就是因为 Timsort 会把数据切成一段段“自然有序”的 run再用归并的方式拼起来对真实数据里常见的局部有序特别友好。3. 核心细节merge 函数里每一处都是坑3.1 双指针合并的正确写法与常见越界merge 的基本形式是双指针。设左段为[lo, mid)右段为[mid, hi)。指针 i 从左段起点出发指针 j 从右段起点出发每次比较a[i]和a[j]把小的那个写进临时数组然后对应指针前进一格。当某一侧指针走到尽头时把另一侧剩余元素整体搬运过去即可。看起来简单但要注意三个细节。第一循环条件是i mid j hi而不是i len j len因为这是区间式实现不能用整段长度。第二某一侧耗尽后的“搬运”必须单独写而不是靠循环自然结束因为循环退出时另一侧还有残留。第三写回原数组的范围是[lo, hi)不是[0, hi)也不是[lo, hi - lo)这个偏移量错误会导致排序结果看似“大部分正确”但在某些位置出现莫名其妙的错乱非常难排查。我见过一个很典型的错误在归并两个子区间时临时数组的下标从 0 开始写写回时却用arr[lo k]结果整体偏移了 lo。这种错误在小数据量下有时能蒙对一旦数组长度上去了就必然翻车。所以我在带新人时都会强调merge 里所有临时数组的下标必须和原数组保持同一套坐标系也就是临时数组也从 lo 开始写写回时直接a[k] tmp[k]逻辑最简单也最不容易错。3.2 临时数组原地合并是真的原地吗很多人说“归并排序需要 O(n) 额外空间”这句话其实不绝对。理论上存在原地归并算法比如基于块交换的实现能把空间压到 O(1)但代价是常数因子非常大实际跑起来比标准版本慢好几倍工程里几乎没人用。所以在日常语境下说归并需要 O(n) 额外空间是准确的。更实际的优化方向是“复用临时数组”。做法是在排序入口处分配一块和原数组等长的缓冲区然后把这块缓冲区的引用传给每一层递归。每一层 merge 都往这块公共缓冲区里写写完立刻写回原数组因为同一层内的 merge 是顺序执行的不会互相干扰。这样整个排序过程只申请一次内存大幅减少分配和回收开销。还有一个细节如果采用“先把左半区复制到临时数组再和右半区比较写回原数组”的写法其实只需要n/2大小的缓冲区。这种写法的好处是写回时右半区的数据还在原数组里没被动过可以直接读。我在 C 实现里经常用这一版因为它把内存需求砍了一半代价是代码稍微绕一点。两种写法在时间上差别不大看个人习惯。3.3 稳定性是怎么保住的为什么必须是小于等于归并排序的稳定性不是天生的而是由 merge 里一个符号决定的。当a[i] a[j]时如果你写的是a[i] a[j]那么左边的元素会先被放进结果左半区的相对顺序得以保留如果写成a[i] a[j]相等时就会让右边的元素先走原本在左边的元素被挤到后面稳定性就破坏了。这一点在排序对象是结构体或者对象时特别重要。比如你要按“订单金额”排序一批订单金额相同的订单希望保持原有下单顺序那这时候就必须用稳定排序。归并排序只要把那个等号加上就天然满足这个需求而快速排序即使你把判断改成由于分区过程中的交换会打乱顺序稳定性依然无法保证。我给一个直观的例子。原始数组是[(A, 3), (B, 1), (C, 3)]按数字排序。归并会把(A, 3)排在(C, 3)前面因为 A 本来就在左边快排则有可能把 C 换到 A 前面。这个差别在报表聚合、日志按时间排序这类场景里会直接影响业务逻辑的正确性。4. 手把手实现三份可以直接用的代码4.1 Python 版本先写清晰版再上原地优化版先给一个最容易理解的版本它的思路是每次递归都返回一个新的有序列表。这段代码适合用来理解算法本身但生产环境不要用因为切片和列表拼接会产生大量临时对象。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(a, b): res [] i j 0 while i len(a) and j len(b): if a[i] b[j]: res.append(a[i]) i 1 else: res.append(b[j]) j 1 res.extend(a[i:]) res.extend(b[j:]) return res生产版本改成区间式加公共缓冲区写法如下。这里把tmp作为参数一路传下去只申请一次内存。def merge_sort_buf(arr): n len(arr) if n 2: return arr tmp [0] * n _sort(arr, tmp, 0, n) return arr def _sort(a, tmp, lo, hi): if hi - lo 2: return mid lo (hi - lo) // 2 _sort(a, tmp, lo, mid) _sort(a, tmp, mid, hi) if a[mid - 1] a[mid]: # 左右已整体有序跳过合并 return _merge(a, tmp, lo, mid, hi) def _merge(a, tmp, lo, mid, hi): i, j, k lo, mid, lo while i mid and j hi: if a[i] a[j]: tmp[k] a[i] i 1 else: tmp[k] a[j] j 1 k 1 while i mid: tmp[k] a[i] i 1 k 1 while j hi: tmp[k] a[j] j 1 k 1 a[lo:hi] tmp[lo:hi]注意if a[mid - 1] a[mid]: return这一句。它的作用是判断左半区最大值是否不大于右半区最小值如果是说明两段拼起来已经有序不需要合并。这个判断对“近乎有序”的数据提升非常明显Timsort 里也有类似思路。4.2 Java 版本arraycopy 与无符号右移Java 版本我把临时数组的复制用System.arraycopy来做它是本地方法比手写循环快。另外计算中点时用(lo hi) 1无符号右移保证 lo hi 溢出时结果依然正确。public class MergeSort { public static void sort(int[] a) { if (a null || a.length 2) return; int[] tmp new int[a.length]; sort(a, tmp, 0, a.length); } private static void sort(int[] a, int[] tmp, int lo, int hi) { if (hi - lo 2) return; int mid (lo hi) 1; sort(a, tmp, lo, mid); sort(a, tmp, mid, hi); if (a[mid - 1] a[mid]) return; merge(a, tmp, lo, mid, hi); } private static void merge(int[] a, int[] tmp, int lo, int mid, int hi) { System.arraycopy(a, lo, tmp, lo, hi - lo); int i lo, j mid; for (int k lo; k hi; k) { if (i mid) a[k] tmp[j]; else if (j hi) a[k] tmp[i]; else if (tmp[i] tmp[j]) a[k] tmp[i]; else a[k] tmp[j]; } } }这段代码里先把整段[lo, hi)复制到 tmp然后从 tmp 里读数据、往原数组 a 里写。这样写的好处是写回阶段逻辑干净不用担心覆盖问题。代价是复制量是完整区间比只复制左半区稍微多一点点但对现代 CPU 来说这点差别可以忽略。4.3 C 版本只复制一半内存的写法C 版本我用“只把左半区拷到缓冲区”的方案临时数组大小开到(n 1) / 2就够。这个写法在内存敏感的场景下更友好也顺便展示一下不同的实现思路。#include vector #include algorithm void mergeHalf(std::vectorint a, std::vectorint buf, int lo, int mid, int hi) { int leftLen mid - lo; for (int i 0; i leftLen; i) buf[i] a[lo i]; int i 0, j mid, k lo; while (i leftLen j hi) { if (buf[i] a[j]) a[k] buf[i]; else a[k] a[j]; } while (i leftLen) a[k] buf[i]; // 右半区剩余元素本来就在原位无需搬运 } void msort(std::vectorint a, std::vectorint buf, int lo, int hi) { if (hi - lo 2) return; int mid lo (hi - lo) / 2; msort(a, buf, lo, mid); msort(a, buf, mid, hi); if (a[mid - 1] a[mid]) return; mergeHalf(a, buf, lo, mid, hi); } void mergeSort(std::vectorint a) { if (a.size() 2) return; std::vectorint buf((a.size() 1) / 2); msort(a, buf, 0, (int)a.size()); }这里有个容易搞混的地方缓冲区坐标从 0 开始而原数组坐标从 lo 开始两套坐标不同。写的时候必须清楚buf[i]对应的是a[lo i]。这种“双坐标系”是这份实现唯一的理解成本写熟了之后反而觉得比全量复制更省事。4.4 自底向上版本不用递归也能归并递归版最大的隐患是栈深度虽然归并的递归深度只有 log n一般不会出问题但在嵌入式或栈空间受限的环境里迭代版本更稳妥。自底向上的思路是从小区间开始两两归并区间宽度从 1 开始翻倍直到覆盖整个数组。def merge_sort_bottom_up(arr): n len(arr) if n 2: return arr tmp [0] * n width 1 while width n: lo 0 while lo n: mid min(lo width, n) hi min(lo 2 * width, n) if mid hi and arr[mid - 1] arr[mid]: _merge(arr, tmp, lo, mid, hi) lo 2 * width width * 2 return arr自底向上的好处是没有递归开销而且很适合做外存排序时的多轮归并因为每一轮的处理逻辑完全一致可以自然地映射到“每轮读文件、归并、写回文件”的流程里。5. 工程实战归并排序真正发光的地方5.1 统计逆序对把 merge 过程当成计数器逆序对问题是我觉得最能体现归并排序价值的应用题。题目是这样的给定一个数组统计有多少对(i, j)满足i j且a[i] a[j]。暴力解法是双重循环 O(n²)数据量上万就卡住了。用归并排序怎么做关键观察是在 merge 阶段当右半区的元素a[j]被选中放进结果时说明它比左半区从 i 到 mid-1 的所有剩余元素都小。这些剩余元素原本都在a[j]左边因为左半区整体在右半区左边所以它们和a[j]构成的都是逆序对。数量正好是mid - i。def count_inversions(arr): n len(arr) tmp [0] * n def rec(lo, hi): if hi - lo 2: return 0 mid (lo hi) // 2 cnt rec(lo, mid) rec(mid, hi) i, j, k lo, mid, lo while i mid and j hi: if arr[i] arr[j]: tmp[k] arr[i]; i 1 else: tmp[k] arr[j]; j 1 cnt mid - i # 关键一行 k 1 while i mid: tmp[k] arr[i]; i 1; k 1 while j hi: tmp[k] arr[j]; j 1; k 1 arr[lo:hi] tmp[lo:hi] return cnt return rec(0, n)我在做数据分析时用这个方法统计过用户行为序列的“乱序程度”比如某个操作流程的实际执行顺序和标准顺序之间有多少倒置算出来的数值可以直接当异常指标用。整个算法在 O(n log n) 内完成比调库再双重循环快了一个数量级。5.2 链表排序归并是链表的最佳搭档链表排序有个尴尬之处快速排序依赖随机访问而链表只能顺序遍历找基准元素和分区都很别扭。归并排序则完全不受影响因为它的核心操作是“顺序遍历 拼接指针”天然契合链表结构而且不需要额外数组空间是 O(log n)只有递归栈。def 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 slow.next slow.next None return merge_two(sort_list(head), sort_list(right)) def merge_two(a, b): dummy node ListNode(0) while a and b: if a.val b.val: node.next a a a.next else: node.next b b b.next node node.next node.next a or b return dummy.next这份代码里用快慢指针找中点这个技巧在很多链表题里都会用到。分割时要注意把slow.next置空否则左边那条链会一直延伸到右边去导致无限递归。这个坑我踩过程序直接卡死调试了半天才发现是分割没断开。5.3 大文件排序分块加多路归并真正让我对归并排序改观的是一次日志处理任务。当时有个几十 GB 的日志文件要按时间戳排序内存根本放不下。解决方案分两步第一步把大文件切成若干块每块控制在内存的四分之一左右读进内存用任意排序算法排好写成一个个临时小文件第二步对这些已经有序的小文件做多路归并用一个最小堆维护“当前每个文件读到的首元素”每次弹堆顶写入结果文件再从对应文件补一个元素进去。import heapq def kway_merge(sorted_lists): heap [] for idx, lst in enumerate(sorted_lists): if lst: heapq.heappush(heap, (lst[0], idx, 0)) out [] while heap: val, li, ei heapq.heappop(heap) out.append(val) if ei 1 len(sorted_lists[li]): heapq.heappush(heap, (sorted_lists[li][ei 1], li, ei 1)) return out堆里存的是三元组第一个元素是值用于比较第二个是链表编号第三个是元素在链表中的下标。这样即使值相同也不会比较后两个字段导致类型错误。实际处理文件时每个sorted_lists[i]换成文件读取迭代器out换成写入缓冲区配合合适的缓冲大小几十 GB 的文件也能在可接受的时间内排完。这就是归并排序在“外存排序”领域的经典应用也是它区别于其他排序算法的最大杀手锏。6. 常见问题排查这些坑我都替你踩过了6.1 运行结果不对时的排查清单归并排序的 bug 大多集中在几处固定的地方我把它们整理成一张速查表遇到问题时按顺序核对基本能定位。现象可能原因排查方向结果部分有序、部分错乱写回下标偏移错误检查写回时是否用了同一坐标系程序卡死不动递归无法收敛检查 mid 计算、区间是否为左闭右开结果出现重复元素临时数组残留旧值检查每轮 merge 是否完整覆盖区间相等元素顺序被打乱判断条件用了小于号改成小于等于以保持稳定数组越界异常hi 传了闭区间值统一约定左闭右开hi 不取大规模数据变慢每层都申请内存改用公共缓冲区只分配一次这里展开说两个最隐蔽的。第一个是“结果部分错乱”这种 bug 最折磨人因为程序不报错只是数据不对。核心原因往往是临时数组的下标用了从 0 开始的坐标系写回却按 lo 偏移导致[0, lo)之外的数据看起来正常实则错位。第二个是“程序卡死”通常是 mid 计算后左右区间没有严格缩小。比如mid lo (hi - lo) / 2如果 lo 和 hi 相差 1mid 就等于 lo左区间是[lo, lo)空集右区间是[lo, hi)和原来一模一样递归永远不会结束。防止这个问题的方法是在递归前先判断hi - lo 2直接返回。6.2 性能不达预期的三个常见原因有些人写完归并排序跑个十万数据发现比标准库的sorted慢好几倍然后怀疑算法本身有问题。其实多数情况下是实现细节拖了后腿。第一个原因是每次 merge 都新建数组。在 Python 里arr[lo:hi]这种切片会创建新对象在 Java 里new int[hi - lo]也一样。修正方法是在顶层分配一次缓冲区往下传引用。第二个原因是死板地合并每个区间没有利用已有顺序。加一句a[mid-1] a[mid]的判断能让近乎有序的数据性能接近线性。我处理过一批日志数据本身只有少量乱序加上这个判断后耗时降到了原来的五分之一。第三个原因是在小数组上继续递归。当区间长度小于 16 左右时插入排序的常数优势会盖过归并的分治开销。标准做法是设置一个阈值小于阈值时切换到插入排序这一步优化通常还能再带来 10% 到 30% 的提升。Timsort 之所以快很大一部分功劳就在这个混合策略上。6.3 关于并发与内存的两点提醒如果你打算在多线程环境里用归并排序要注意临时数组不能共享。每个线程必须有自己独立的缓冲区否则两个线程同时往同一块内存写数据会出问题。另外归并排序的递归部分天然可以并行化——左右两个半区彼此独立丢到线程池里跑就行。但线程创建本身有开销只有数据量足够大比如百万级以上时才值得并行小数据量并行反而更慢。内存方面除了缓冲区本身还要留意对象的引用情况。在 Java 里归并排序对象数组时临时数组持有的是对象引用不会复制对象本身所以额外内存开销主要是引用数组不是对象数据。这一点在排序大对象时很关键因为对象本身可能很大但引用只需要几个字节。7. 几个容易被忽略的进阶话题7.1 多路归并与败者树两路归并是最常见的形式但当有序文件数量很多时每次比较两个文件效率不高。这时可以用多路归并一次从 k 个文件中选最小值。选最小值如果用线性扫描代价是 O(k)如果用堆代价降到 O(log k)而败者树能做到几乎同样的效率且常数更小所以在专业的排序库和数据库实现里败者树是标准配置。理解败者树的前提是先理解两路归并的“比较-选择”模型把这个模型推广到 k 路就成了败者树。7.2 归并思想在其他算法里的影子逆序对只是归并思想的一个应用同样的“分治加合并”框架还能解决很多问题。比如求数组中的“重要逆序对”前一个元素大于后一个元素的两倍只要在 merge 时改一下比较条件即可再比如计算“区间和的个数”也可以借助归并过程中的有序性做统计。这种把排序过程和统计过程融合在一起的技巧在算法竞赛里非常常见本质上都是在利用归并过程中“子区间已经有序”这个不变量。我个人的经验是把归并排序当成一个“可编程的排序框架”来看待而不仅仅是一个排序函数。它的 merge 阶段是一个天然的钩子你想在合并过程中统计什么、判断什么都可以往里插。这种灵活的延展性是快速排序和堆排序都不具备的。
