1. 从一道排序题说起为什么归并排序值得认真学很多人接触归并排序都是从算法课或者面试题开始的。一般教材会告诉你归并排序是典型的分治算法时间复杂度稳定在 O(n log n)空间复杂度 O(n)。听起来很标准但真让自己动手写一遍或者解释清楚“为什么它比快速排序更稳定”“为什么它适合排序链表”“为什么外部排序也靠它”一半以上的人会卡壳。我最早认真研究归并排序是在处理一个实际需求的时候有一批日志文件每个文件内部已经按时间排好了序但文件之间是乱序的需要把所有记录合并成一个全局有序的大文件。如果直接全部读进内存排序数据量太大内存扛不住如果每次把所有文件都扫描一遍选最小值时间复杂度又高得离谱。后来我意识到这其实就是多路归并问题而归并排序的核心思想——两个有序序列的合并恰恰是这一切的地基。所以这篇不是我复述教材定义而是从“为什么要用它”“它本质在解决什么”“代码怎么写不踩坑”“真实场景里怎么变通”这几个角度把归并排序彻底讲透。无论是准备面试、应付考试还是要在工程里做排序、合并、外部排序这篇文章都能给你一套可以直接用的思路和代码。2. 归并排序的核心算法拆解分、治、合的三步哲学2.1 分而治之不是空话它是递归问题的通用解法归并排序的整个流程可以浓缩成三个动作分解、递归排序、合并。听起来简单但里面有两个关键洞察。第一个洞察把大规模问题拆成两个规模减半的子问题递归地去解决最后把结果组合起来。这个思路本身不是排序特有的二分查找、快速排序、二叉树遍历都是同一套路。归并排序的特殊性在于它保证拆分之后两个子数组各自有序然后通过一个线性时间的合并操作就能得到全局有序。因为拆分是严格的“切一半”所以递归深度是 log n每一层合并的总工作量是 O(n)总复杂度 O(n log n)。第二个洞察归并排序的性能不依赖于输入数据的初始状态。快速排序的平均复杂度是 O(n log n)但最坏情况下会退化到 O(n^2)原因在于基准点选择不好会导致分治不平衡。而归并排序永远是“对半切”无论数据是正序、逆序、全相等还是完全随机递归树都是平衡的时间复杂度永远稳定在 O(n log n)。这个特性在实际系统中很值钱——你不需要担心某个特殊数据让排序突然变慢。2.2 合并两个有序数组整个算法的心脏假设我们有两个已经排好序的子数组左半部分[1, 3, 5]右半部分[2, 4, 6]要合并成[1, 2, 3, 4, 5, 6]。最朴素的想法是把两段拼在一起再整体排序但那样合并复杂度就成了 O(n log n)整个算法就退化了。正确做法是使用双指针指针 i 指向左子数组开头指针 j 指向右子数组开头。比较left[i]和right[j]谁小就把谁放入结果数组对应指针后移。如果某一边先走完直接把另一边剩下的元素全部拷贝到结果尾部。这个过程每次比较都能确定一个元素的最终位置所以合并 n 个元素的复杂度是 O(n)。这也是归并排序“合并”这一步的绝对核心。我见过很多初学者写合并时喜欢把两个临时数组合并后覆盖回原数组逻辑上没错但容易忽略边界条件。更稳妥的做法是在合并前先拷贝一份[low..high]的副本到临时数组然后用三个下标i, j, k分别指向左半起点、右半起点、原数组写入位置。这样写的好处是不用区分“哪一个临时数组”只用一个temp代码更短边界更清晰。2.3 递归与迭代两种姿势的取舍归并排序有两个实现方向一个是自顶向下的递归一个是自底向上的迭代。递归版本就是标准的分治实现sort(arr, low, high)当low high时取中点mid (low high) / 2分别排序左右区间然后执行merge(arr, low, mid, high)。递归实现最符合思维直觉代码也短但有一个隐患递归深度是 O(log n)在极端大数组上虽然不至于爆栈但函数调用和栈帧切换有额外开销。迭代版本也叫自底向上归并思路是从长度为 1 的子数组开始先两两合并成 size2 的有序块再两两合并成 size4 的有序块直到整个数组有序。核心是控制步长size从 1 翻倍到 n内层循环按size切块合并相邻的两块。这个版本写起来稍微绕一点但避免了递归调用而且特别适合对外部排序、文件分块合并做优化因为你可以控制每次只处理一个块的大小内存占用是可控的。实战中我一般建议先理解递归版能画清楚递归树、能写出代码等真正做大数据场景时再切到迭代版或优化版。两个版本混着理解面试时反而能体现出深度。3. 归并排序代码实现与参数细节从伪代码到工程级写法3.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(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这个版本最容易理解适合初学者快速跑通逻辑。但它有两个问题第一每次递归都创建left和right两个新切片以及result结果列表频繁分配内存空间开销大数据量上来之后性能明显下降。第二这不是原地排序合并时必须使用额外空间。这一点务必要理解归并排序的时间复杂度是 O(n log n)但空间复杂度是 O(n)。有些人面试时说“归并排序空间复杂度 O(1)”这是不对的除非你做了极复杂的原地归并技巧否则标准实现一定是 O(n) 额外空间。如果你的目标是现场快速演示算法思路上面这个版本就够了。但想要它像一个工程级的写法就得改成下面这种“就地但使用临时数组”的版本。3.2 原地归并的标准模板Java/Python 通用思路真正在项目中会用的是一个在递归过程中复用同一个临时数组的版本。以 Java 为例代码如下public class MergeSort { public static void mergeSort(int[] arr) { if (arr null || arr.length 2) return; mergeSort(arr, 0, arr.length - 1); } private static void mergeSort(int[] arr, int low, int high) { if (low high) return; int mid low ((high - low) 1); mergeSort(arr, low, mid); mergeSort(arr, mid 1, high); merge(arr, low, mid, high); } private static void merge(int[] arr, int low, int mid, int high) { // 拷贝需要合并的区间到临时数组 int[] temp new int[high - low 1]; int i low, j mid 1, k 0; while (i mid j high) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j high) temp[k] arr[j]; // 写回原数组 for (int p 0; p temp.length; p) { arr[low p] temp[p]; } } }这段代码有几个细节值得说一是mid low ((high - low) 1)很多教材写(low high) / 2但low high在极端情况下比如数组长度接近Integer.MAX_VALUE可能溢出右移写法更安全。二是合并时把arr的对应区间复制到temp而不是复制整个arr。这样每次合并临时数组的长度只跟当前区间有关总空间复杂度还是 O(n)但实际分配次数少了性能更好。三是合并时的比较用而不是。这个细节对“稳定性”很重要。归并排序是稳定排序也就是相等的元素在排序后保持原来的相对顺序。如果用相等时会把右半边的元素先放进结果左半边等值元素的相对位置就会翻转稳定性就被破坏了。所以写是保持稳定性的关键。3.3 自底向上迭代实现一次看透归并的步长控制递归解法的思维是“从整体拆到最小”迭代解法的思维是“从最小建到整体”。用 Python 写一个迭代版本def merge_sort_iter(arr): n len(arr) size 1 # 临时数组只分配一次 temp [0] * n while size n: for low in range(0, n, 2 * size): mid min(low size - 1, n - 1) high min(low 2 * size - 1, n - 1) if mid high: merge(arr, temp, low, mid, high) size * 2 return arr def merge(arr, temp, low, mid, high): i, j, k low, mid 1, low while i mid and j high: 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 high: temp[k] arr[j]; j 1; k 1 # 写回 arr for p in range(low, high 1): arr[p] temp[p]这里的关键是边界计算。size 表示当前每个有序块的长度。合并时当前块的左半区间是[low, mid]右半区间是[mid1, high]。low 每次加2 * size但数组末尾可能不足两个完整块所以 mid 和 high 都要用min封顶防止越界。自底向上的好处是它天然适合对磁盘文件排序你可以设置一个合理的size比如 256MB每次只在内存中处理两个块合并后写回磁盘再处理下一批。这就是外部归并排序的雏形。我后面会详细讲。3.4 优化技巧插入排序助攻 哨兵位提速归并排序有一个很大的优化点是当递归到很小规模时比如数组长度小于某个阈值递归下去的成本可能高于直接插入排序。因为递归每深入一层都有函数调用开销、临时数组分配开销而插入排序在小数组上实际非常快因为它利用了 CPU 缓存局部性几乎没有额外空间。所以在工程实现里可以在mergeSort的递归函数开头加一个判断private static void mergeSort(int[] arr, int low, int high) { if (high - low 1 16) { insertionSort(arr, low, high); return; } int mid low ((high - low) 1); // ... }阈值一般是 7 到 32 之间实际测试中 16 是个不错的默认值。这样既保留了归并排序的整体稳定性又避免了小规模递归的开销。另一个优化是“哨兵位”。合并时我们通常需要判断 i 是否越界、j 是否越界每次循环都要检查。如果用哨兵可以在左半数组末尾放一个Integer.MAX_VALUE右半数组末尾也放一个Integer.MAX_VALUE这样比较到最后一定其中一个先触到哨兵而哨兵值不会进入结果。代码会简化成只有一个循环每轮只比left[i]和right[j]。不过哨兵法要求数组允许额外存储哨兵而且如果原始数据本身就含有Integer.MAX_VALUE会出错所以实战中用得不如阈值优化多。4. 归并排序的复杂度真相时间、空间、稳定性一个都不能漏4.1 为什么时间复杂度恒为 O(n log n)归并排序的时间复杂度可以这样严格推导设 T(n) 为对 n 个元素排序的时间。递归时拆成两个规模为 n/2 的子问题加上合并的 O(n) 时间得到递推式T(n) 2T(n/2) O(n)展开可得T(n) 2[2T(n/4) O(n/2)] O(n) 4T(n/4) 2O(n)继续展开直到 T(1) O(1)递归深度为 k当 n 2^k 时k log n。每一层合并的总时间都是 O(n)所以总时间T(n) O(n) * log n O(n log n)这个推导不是背公式而是理解“每一层都做了 O(n) 的总工作量一共有 log n 层”这个直观图景。4.2 空间复杂度 O(n) 从哪里来很多人以为归并排序的空间复杂度是 O(n log n)因为每一层都申请临时数组。实际上如果每个递归层都申请一块与当前区间等长的临时数组并在合并后释放那么任意时刻所有递归栈中活动区间临时数组的大小之和不超过 O(n)。举个小例子第一层申请 n 大小的临时数组但它在等待第一层合并时第二层的两个区间总共也是 n 大小。不管递归怎么展开同一时刻的临时数组总量不超过 n。所以空间复杂度是 O(n)。如果每次合并时都新建一个临时数组运行时的内存分配器开销会让性能变差。所以我建议把临时数组定义成成员变量在排序前一次性分配new int[arr.length]递归过程中直接复用。这样空间开销还是 O(n)但分配次数降为 1性能明显更好。4.3 稳定性的价值被很多人低估了排序算法的稳定性指的是如果两个元素的 key 相等排序后它们的相对位置不变。归并排序是稳定的只要合并时相等元素的顺序保持“先左后右”。上面代码里用已经保证了这一点。稳定性在真实系统里非常有用。比如你有一份人员数据先按部门排序再按年龄排序如果年龄相同的员工不希望在第二次排序后打乱原先的部门顺序那就必须用稳定排序。SQL 里的 ORDER BY 多层排序底层用的就是稳定排序。快速排序通常是不稳定的所以如果需要保持相对顺序归并排序是默认选择。数组排序时你可以在内存中随意搬移元素稳定不稳定好像无所谓但如果排序对象是链表、外部文件或者元素很大不便于整体搬移稳定性就成硬性要求了。5. 进阶实战一归并排序解决“小和问题”与“逆序对问题”5.1 小和问题归并排序副产品有一个经典面试题给定数组对每一个数把左边所有比它小的数求和把所有这样的和累加起来叫做“小和”。比如[1, 3, 4, 2]1 左边没有比它小的贡献 03 左边比它小的只有 1贡献 14 左边比它小的有 1、3贡献 42 左边比它小的有 1贡献 1总小和 1 4 1 6暴力方法二重循环是 O(n^2)但归并排序可以在 O(n log n) 时间内解决。关键是利用合并时子数组已经有序当左边数组元素arr[i]小于等于右边数组元素arr[j]时说明右边[j..high]中的所有元素都比arr[i]大那么arr[i]对整体小和的贡献就是arr[i] * (high - j 1)。在合并过程中累加这些贡献即可。代码片段public class SmallSum { private static int sum 0; public static int smallSum(int[] arr) { sum 0; int[] temp new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); return sum; } // 在 merge 中当 left[i] right[j] 时 // sum left[i] * (high - j 1); }为什么能在合并时算因为合并前左右两边已经各自有序当left[i]小于等于right[j]时left[i]一定小于等于右半边从 j 开始的每一个数。这样一下子算出了多个“小和”把单个 O(n) 的累加优化成了 O(1) 的乘法整个算法时间复杂度也从 O(n^2) 降为 O(n log n)。5.2 逆序对问题一个归并排序能算出的经典指标逆序对的定义是对数组中的两个元素i j如果arr[i] arr[j]它们构成一个逆序对。求逆序对数量同样是经典题。暴力解法 O(n^2)用归并排序可以降到 O(n log n)。在合并过程中如果当前左边元素left[i] right[j]那么左半边从 i 到 mid 的所有元素都大于right[j]因此right[j]和左半边剩下的每个元素都构成逆序对。所以逆序对数量可以一次性累加mid - i 1。这里巧妙的地方是合并时左右两边已经有序所以当right[j]被选中弹出时左半边剩余的所有元素都比它大直接算出跨区间的逆序对数再加上递归过程中左右子数组内部的逆序对数整棵递归树算完就是全局逆序对总数。这两个问题本质上都在吃“合并时两个子数组有序”的红利。理解了这一点你就会明白为什么归并排序除了排序本身还能顺手解决一堆区间统计问题。6. 进阶实战二排序链表的归并排序实现数组归并排序稍微有点麻烦的地方是额外空间。但如果排序对象是链表归并排序反而变成了最优选择因为链表节点不需要连续内存合并时只需要改指针不需要额外数组空间复杂度能降到 O(log n)仅递归栈。链表归并排序的思路用快慢指针找到链表的中点递归排序左右两半合并两个有序链表找中点是关键步骤。一个典型实现public ListNode sortList(ListNode head) { if (head null || head.next null) return head; ListNode slow head, fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } ListNode rightHead slow.next; slow.next null; // 断开 ListNode left sortList(head); ListNode right sortList(rightHead); return mergeTwoLists(left, right); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } if (l1 ! null) cur.next l1; if (l2 ! null) cur.next l2; return dummy.next; }注意fast head.next这个细节。如果写成fast head当链表只有两个节点时快慢指针会出现问题。使用fast head.next可以在偶数长度节点时让 slow 停在上中点保证左右分割均匀。链表归并排序的空间复杂度 O(log n)时间复杂度 O(n log n)这在所有排序算法里都很有竞争力。所以很多语言的标准库在排序链表时会直接选择归并排序。7. 进阶实战三外部排序与多路归并回到我开头提到的日志文件合并问题。当时文件总大小远超内存没法一次性加载标准做法就是“外部多路归并排序”。外部排序的核心步骤把大文件切分成若干个小块每个小块都能加载进内存。用快速排序或内存归并排序把每个小块排好序写回磁盘形成若干个有序段。把所有有序段进行“多路归并”每次从每个段中读取当前最小的元素用小顶堆维护堆顶就是全局最小取出后继续读对应段的下一个元素。这里用到的核心数据结构就是“堆”但堆本质上是在做多路归并的“选择最小者”操作。对比我们前面讲的二路归并多路归并就是 K 个指针每次选择 K 个指针中最小值。如果每次线性扫描 K 个指针每输出一个元素就要 O(K)代价太高用大小为 K 的最小堆每次取堆顶 O(1)堆调整 O(log K)总复杂度大幅降低。在实现多路归并时相邻的两个有序段合并只是特例。真正工程中归并排序的思想被无限放大大文件 → 内存块排序 → 多路归并 → 全局有序。这就是所有数据库排序、大数据排序的基础。需要说明的是外部排序的很多细节比如缓冲区设计、预读、归并路数选择非常讲究但万变不离其宗二路归并的“两个有序序列合二为一”是所有复杂归并策略的最小原子。8. 归并排序 vs 快速排序现实场景里的取舍我在很多场合被问到“归并排序和快速排序到底选哪个”。这取决于场景。时间复杂度上归并排序稳定 O(n log n)快速排序平均 O(n log n) 但最坏 O(n^2)。空间复杂度上归并排序 O(n)快速排序 O(log n)递归栈。稳定性上归并排序稳定快速排序不稳定。因此在内存充足且对稳定性有硬性要求时归并排序是首选。Java 的Collections.sort对对象使用归并排序TimSort 本质上是归并排序的改进版就是这个原因。而Arrays.sort对基本类型使用快速排序是因为基本类型不需要稳定性并且更在意常数因子和内存占用。在数据量大到内存放不下时归并排序思想是外部排序的基础。在数据量小或者可以用内存排序时快速排序通常因为更优的缓存局部性实际跑起来更快。我这里说的代码性能通常是实测而不是理论快速排序对 int 数组一般比归并排序快 1.2 到 1.5 倍因为它无序额外数组也不怎么影响缓存。如果数组长度很小比如小于 50直接插入排序甚至比快排、归并都快。工程上还有折中方案比如混合排序当递归分割到小数组时用插入排序当排序对象是对象时使用稳定归并排序当排序对象是基本类型时使用双轴快排。这些策略都被纳入标准库了理解归并排序的原理后再看标准库源码会豁然开朗。9. 常见问题与排查技巧实录9.1 合并时数组越界新手最容易犯的错是合并循环里没有正确判断i mid和j high导致一个子数组已经耗尽还在访问它的元素。正确写法是在主 while 循环条件里同时判断两个下标循环结束后再单独处理剩余元素。如果你用的是while (i mid j high)这种写法越界风险就小很多。还有一个隐蔽问题自底向上归并时mid和high计算错误。很多人直接写mid low size - 1忘了对n-1做 min 限制。当数组末尾不足一个完整块时mid可能超出数组长度导致合并时越界。解决方法是mid min(low size - 1, n - 1) high min(low 2 * size - 1, n - 1) if mid high: merge(...)9.2 递归栈溢出深度递归有栈溢出风险吗理论上归并排序递归深度是 log nn 为 10^9 时深度也只有 30 层远不会爆栈。但如果你用递归版对超长链表排序递归深度还是 log n也没问题。真正可能爆栈的是递归函数的局部变量太多、或者使用了巨量临时数组。如果担心就用自底向上迭代版。9.3 临时数组分配过于频繁如果每层递归都new int[high-low1]数据量大时会频繁触发 GC运行速度变得很慢。我实际测试过对一个 10 万随机数排序频繁分配临时数组的方法比复用同一数组的方法慢 3 倍以上。所以工程写法务必在排序前分配一次temp new int[arr.length]合并时拷贝对应区间。9.4 稳定性测试怎么验证可以写一个简单的测试用例构造一个二维数组每个元素包含两个字段第一字段作为排序 key第二字段用于标记原始顺序。排序后检查所有 key 相等的元素是否保持原始相对顺序。如果相等元素的 second 字段是递增的说明算法稳定。int[][] data {{1,0}, {2,1}, {1,2}, {3,3}}; // 按第一列排序稳定的话key1 的两个元素顺序保持 [0,2]9.5 归并排序是原地排序吗不是。标准归并排序必须用额外空间合并空间复杂度 O(n)。有些论文提出了原地归并in-place merge通过复杂旋转和交换实现 O(1) 额外空间但常数因子太大实际很少用。面试时如实回答“标准实现需要 O(n) 辅助空间”就好别为了显得厉害说自己能做 O(1) 空间除非你真做过深入研究。9.6 为什么用哨兵位可能出问题如果数组元素本身可以等于你选的哨兵值比如Integer.MAX_VALUE哨兵会被当作正常元素参与比较导致错误。如果真的用哨兵必须确保输入数据中不可能出现该值。更稳妥的做法是用条件判断处理剩余元素代码虽然多几行但没有风险。10. 总结我建议你亲手写三遍归并排序如果看完这篇文章你只记住一个操作我建议你亲手写三遍归并排序。第一遍写递归版重点理解分治和合并的边界条件。第二遍写自底向上迭代版重点理解 size 翻倍与 mid/high 边界计算。第三遍写链表归并排序重点理解快慢指针找中点和dummy节点的用法。写完三遍后再去做小和问题、逆序对问题你会发现所有代码里都藏着同一个灵魂两个有序序列的合并动作。当你能把这个最小动作背后的逻辑讲清楚——为什么合并一个长度 n 的序列是 O(n)为什么相等时选左不选右为什么左边剩余元素可以直接拼接——你才算真正掌握归并排序而不是背了一个模板。顺便提一个好习惯每次写完排序算法后马上用几组测试数据检查结果。比如[]、[1]、[3,1,2]、[5,5,5,1]、[10,9,8,7,6,5,4,3,2,1]这些边界用例能暴露代码里绝大多数隐藏问题。归并排序不是我所有排序算法里代码最简的但它一定是扩展性最强的。从最简单的数组排序到逆序对计算再到链表排序、外部多路归并甚至数据库里的归并连接全都能归到这一个思想下。把地基打牢后面的高楼盖起来就不费力了。