1. 为什么几乎每本算法书都要讲归并排序先聊聊它的“江湖地位”我第一次认真学归并排序Merge Sort的时候其实挺不以为然的——不就是“分半、递归、合并”三步走吗代码写起来也没有快排那种“一针见血”的爽感。但后来真正用它去处理实际数据被它狠狠教育过几次之后我才发现归并排序才是那个“看着低调但永远不会让你翻车”的稳定选手。如果你是刚开始接触算法的读者可以先建立起一个基本印象归并排序是一种基于“分治思想”的排序算法。它的核心操作是把一个乱序数组不断拆成两半直到每个子数组只剩一个元素天然有序然后再把这些有序子数组两两合并最终得到整体有序的结果。这个思想朴素到什么程度呢你可以把它想象成整理一副打乱的扑克牌先把牌堆分成两堆再分再分直到每一堆只有一张牌然后每次拿两堆牌从头开始比较大小按序合成一堆更大的牌堆重复这个过程直到重新合成一整副有序的牌。我为什么说它“低调”因为从平均性能上看归并排序的时间复杂度稳定在 O(n log n)这一点和快排、堆排属于同一梯队。但归并排序有一个快排最羡慕不来的优点稳定性。直接用代码跑一遍你会发现无论是完全随机的数据、近乎有序的数据还是带着大量重复值的数据归并排序的性能波动都很小而且它不会像快排那样在最坏情况下退化到 O(n²)。这篇文章我会把归并排序从原理到实现彻底讲透包括分治结构到底怎么拆、合并过程为什么能做到线性复杂度、递归写法的时间复杂度推导、迭代式自底向上归并怎么写以及你真正写代码时最容易踩的坑。我不只会给出 Java 和 Python 的完整实现还会带你分析为什么有些写法慢、有些写法省内存、什么时候该用归并排序而不是其他排序。如果你正在准备面试、刷 LeetCode或者需要在业务代码里手写一个稳定的排序工具这篇文章应该能帮你少走很多弯路。2. 先拆开看“分”和“治”归并排序的核心结构到底长什么样2.1 分治法的灵魂把一个复杂问题拆成可独立解决的小问题归并排序背后的分治思想其实不只是排序领域的基础更是很多高级算法比如线段树、CDQ 分治、整体二分的基石。分治法的套路总结起来就是三个动作分解Divide、解决Conquer、合并Combine。对归并排序来说分解把长度为 n 的数组从中点一分为二得到两个长度约为 n/2 的子数组。解决递归地对两个子数组分别进行归并排序。递归的终止条件是子数组长度为 1 或 0——长度为 1 时数组天然有序不需要再排。合并把两个已经有序的子数组通过线性扫描的方式合并成一个有序数组。你会发现分解和解决阶段实际上没有做任何“比较大小”的操作所有的排序工作都发生在合并阶段。我一开始自学的时候总觉得奇怪排序的“重活”不在拆分而在合并那拆分的意义是什么后来想明白了拆分的作用是把大数组逐步缩小到“天然有序”的不可再分单元然后通过一次次合并把有序性从一个元素逐步“传染”到整个数组。就像盖房子拆分是在预制砖块合并是在砌墙两者缺一不可。2.2 合并两个有序数组整个算法里真正干活的部分假设你有两个已经排好序的数组比如left [1, 3, 5]和right [2, 4, 6]要合并成一个整体有序的数组。你会怎么做最自然的做法是拿两个指针分别指向 left 和 right 的起始位置比较两个指针指向的元素谁小就把谁放到结果数组里然后相应指针向后移动。某一方的指针先走到头后把另一方剩下的元素全部拼接到结果数组尾部。合并过程的时间复杂度是 O(m n)其中 m、n 是两个子数组的长度。因为两个子数组各自有序所以线性扫描一遍就能完成合并不需要任何额外比较的“回溯”。这也是归并排序整体能保持 O(n log n) 的关键——合并这一步是线性的而递归深度是 log n 层。合并操作用代码写出来大概是这样的逻辑伪代码风格function merge(left, right) { let result []; let i 0; // 指向 left 的指针 let j 0; // 指向 right 的指针 while (i left.length j right.length) { if (left[i] right[j]) { result.push(left[i]); i; } else { result.push(right[j]); j; } } // 把剩余部分直接拼接 while (i left.length) { result.push(left[i]); i; } while (j right.length) { result.push(right[j]); j; } return result; }需要注意的是当left[i]和right[j]相等时我写的是取left[i]。这一点看似无所谓实际上是归并排序稳定性的来源。所谓“稳定”就是值相等的元素在排序前后的相对顺序保持不变。取左数组的相等元素入队就能保证原本在前的更小的索引对应的元素仍然排在前面。如果你把left[i] right[j]改成那相等时会先取右数组的元素稳定性就被破坏了。后面我会专门讲稳定性的实际意义。2.3 递归拆分的完整过程从 [5, 2, 4, 6, 1, 3] 手推一遍理论说完了我们来手动走一遍完整的归并排序过程这样你对“分—治—合”的印象会更立体。假设数组是[5, 2, 4, 6, 1, 3]长度为 6中点索引是(0 5) // 2 2这里用整数除法。第一层拆分左半部分[5, 2, 4]右半部分[6, 1, 3]对左半部分继续拆中点索引(0 2) // 2 1左半部分[5, 2]右半部分[4][5, 2]继续拆成[5]和[2]此时[5]和[2]都已经是长度为 1 的有序数组开始合并比较 5 和 22 小得到[2, 5]将[2, 5]和[4]合并比较 2 和 42 入比较 5 和 44 入5 剩余得到[2, 4, 5]左半部分排好了。对右半部分[6, 1, 3]做同样的事拆成[6]和[1, 3][1, 3]继续拆成[1]和[3]合并[1]和[3]得[1, 3]合并[6]和[1, 3]比较 6 和 11 入比较 6 和 33 入6 剩余得到[1, 3, 6]最终合并左半[2, 4, 5]和右半[1, 3, 6]2 对 11 入2 对 32 入4 对 33 入4 对 64 入5 对 65 入6 剩余入得到最终结果[1, 2, 3, 4, 5, 6]。这里有一个值得注意的细节每一层的合并结果都是局部有序的但只有在最顶层合并完成后整个数组才完全有序。如果你在递归中途打印中间状态会看到很多半有序的子数组交叉存在。理解这个层次感很重要否则你在调试归并排序时容易被“中间状态比输入还乱”的假象误导。3. 时间复杂度与空间复杂度为什么是 O(n log n)推导过程一次讲清3.1 时间复杂度递归树展开法帮你直观理解很多资料直接告诉你归并排序的时间复杂度是 O(n log n)但没讲清楚这个 log n 怎么来的。我们不妨用递归树来推导。设 T(n) 表示对长度为 n 的数组进行归并排序所需的时间。归并排序把一个规模为 n 的问题分解成两个规模为 n/2 的子问题每个子问题解决后还要做一次合并。合并两个长度为 n/2 的数组需要扫描整段元素耗时是 O(n)。所以有递推式T(n) 2 * T(n/2) O(n)展开一层T(n/2) 2 * T(n/4) O(n/2)所以 T(n) 2 * [2 * T(n/4) O(n/2)] O(n) 4 * T(n/4) 2 * O(n/2) O(n) 4 * T(n/4) 2 * O(n)等等这里 2 * O(n/2) O(n)再加 O(n) 得到 2 * O(n)。继续展开T(n) 8 * T(n/8) 3 * O(n)你可能会发现规律展开 k 层后有 2^k 个规模为 n/2^k 的子问题合并总代价是 k * O(n)。当子问题规模缩小到 1 时有 n/2^k 1即 k log2 n。此时有 n 个规模为 1 的子问题每个子问题的解决时间是常数 O(1)。于是整体复杂度是T(n) O(n) * log2 n O(n) O(n log n)另一种更工程化的理解方式每一层都会对所有元素扫描一遍一共扫描 log n 层。归并排序把一个长度为 n 的数组拆到单个元素层数是 log2 n因为每层减半每一层的合并操作会涉及 n 个元素的比较和移动所以总时间是 n * log n。这个视角在写代码时特别有用——你每增加一层递归就多付出一次“全体扫描”的代价。3.2 最坏、最好、平均复杂度为什么归并从不受输入顺序影响这是归并排序和快排最大的差异点之一。快排的最好时间复杂度是 O(n log n)最坏是 O(n²)平均是 O(n log n)证明比较复杂涉及随机性与概率分析。而归并排序无论输入数据是什么顺序它的拆分方式永远是从中点一刀切递归结构完全一样合并时虽然比较次数会有细微差异但整体仍然保持 O(n log n) 的复杂度。我们来细看无论是有序数组、逆序数组还是随机数组归并排序都会经历同样次数的“拆分—合并”。唯一有差异的是合并阶段比较的次数。比如合并两个有序数组时如果前一个数组的所有元素刚好都小于后一个数组的第一个元素那么比较次数等于前一个数组的长度 m如果两个数组的元素交错得很厉害比较次数可能接近 m n。但不管怎样比较次数都在 m n - 1 这个量级以内所以整体时间复杂度的上界还是线性的。把这层结论推广到所有层就能严格说明归并排序的最坏情况也是 O(n log n)。这种“不挑输入”的特性在实际应用中价值很大。举个业务场景你有一个服务端接口需要对接多种来源的数据——有的上游已经排好序比如数据库按主键导出有的完全乱序比如用户上传的 Excel有的还可能带大量重复。如果直接用快排面对已经排好序的极端输入可能退化到 O(n²)需要额外引入随机化或者三路切分才能兜底。这时候用归并排序就安心得多它的性能曲线几乎是平直的。3.3 空间复杂度O(n) 的额外空间到底花在哪了很多人第一次看归并排序的教科书实现时会困惑明明每次只合并两个子数组为什么空间复杂度是 O(n) 而不是 O(log n)原因很简单——归并排序需要一个额外的临时数组来存放合并结果而这个临时数组的长度是 n。常见的递归实现里每个合并过程都会新建一个临时数组来存合并后的结果。虽然每一层递归中会有多个临时数组但它们在使用后会被回收同一时刻占用空间的临时数组大小总和不会超过 n。比如最顶层合并时临时数组长度是 n这一层合并结束后临时数组被释放下一层才创建长度为 n/2 的两个临时数组。所以空间复杂度是 O(n)而不是每一层相加的 O(n log n)。不过这里有个容易被忽视的实现细节很多教材为了代码简洁喜欢在递归函数内部创建新数组这样写确实好理解但会带来频繁的数组分配和垃圾回收开销在 Java 和 C 这类语言中尤其影响性能。更推荐的做法是在排序入口处一次性申请一个与原数组等长的临时数组然后递归时通过索引区间反复使用这一块内存。这样既保持了 O(n) 的空间复杂度又避免了大量中间对象的创建。后文我会给出这种实现的具体代码。3.4 稳定性到底是什么为什么业务排序经常死磕这一点稳定性是一个容易被人忽略、但面试和实际业务中都非常重要的属性。我举个例子你就明白了。假设你有一个学生列表每个学生有班级编号和考试成绩两个字段。你先按成绩从高到低排序然后在保持成绩排序不变的前提下再按班级编号排序。如果排序算法是稳定的那么相同班级的学生按成绩排序的前后关系不会被打乱如果算法不稳定第二次排序后同班学生之间的成绩顺序可能变得乱糟糟的。这个场景对应到真实业务里非常常见电商平台先按“优惠金额”排序再按“商品类目”分组展示数据库执行ORDER BY a, b时也需要稳定的排序手段。归并排序因为合并时“优先取左数组元素”天然是稳定的这也是它在数据库底层排序比如 PostgreSQL 的某些排序路径中被青睐的主要原因。反观快排的经典单轴实现一般是不稳定的除非你刻意做特殊处理这也是为什么在某些场景下即使快排平均性能更好工程师仍会选择归并排序的理由之一。4. 动手写代码Java 和 Python 的两种主流实现模式4.1 递归式自顶向下归并排序最符合直觉的写法先来看 Java 的递归式归并排序重点展示“一次性分配临时数组”的优化写法。我强烈建议你不要在递归函数里每次创建新数组而是把临时数组作为参数传入并用索引定位当前需要合并的区间。public class MergeSort { public static void mergeSort(int[] arr) { if (arr null || arr.length 2) { return; } int[] temp new int[arr.length]; sort(arr, 0, arr.length - 1, temp); } private static void sort(int[] arr, int left, int right, int[] temp) { // 递归终止条件区间内少于两个元素 if (left right) { return; } int mid left (right - left) / 2; // 防止 left right 溢出 sort(arr, left, mid, temp); sort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } private static void merge(int[] arr, int left, int mid, int right, int[] 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 p left; p right; p) { arr[p] temp[p]; } } }这里有几个细节值得单独说int mid left (right - left) / 2而不是(left right) / 2是为了防止 left 和 right 都很大时整数溢出。很多人在小数组上测试没问题一到大数组就翻车就是这个原因。merge函数把结果先写到临时数组再拷贝回原数组。有人可能会问能不能直接写到原数组不能因为合并时左右子数组的值都还存放在原数组对应位置如果直接覆盖原数组的左边部分可能会把尚未读取的右半区间元素覆盖掉。临时数组在这里起着“读保护”的作用。当arr[i] arr[j]时选择左元素这保证了稳定性。如果写成相等时取右元素稳定性就会丢失。测试一下public static void main(String[] args) { int[] arr {9, 5, 2, 7, 1, 8, 3, 6}; mergeSort(arr); System.out.println(Arrays.toString(arr)); } // 输出 [1, 2, 3, 5, 6, 7, 8, 9]4.2 Python 的递归实现简洁但要注意切片开销Python 的递归归并排序写起来非常简洁但有一个常见的陷阱如果使用left arr[:mid]和right arr[mid:]这样的切片写法每层递归都会创建新的列表。虽然看起来干净但切片操作本身会复制数据导致额外的时间和空间开销。对于小规模数据无所谓数据量大了以后性能会明显下降。我建议的写法是使用索引区间避免多次复制def merge_sort(arr): if arr is None or len(arr) 2: return arr temp [0] * len(arr) _sort(arr, 0, len(arr) - 1, temp) return arr def _sort(arr, left, right, temp): if left right: return mid left (right - left) // 2 _sort(arr, left, mid, temp) _sort(arr, mid 1, right, temp) _merge(arr, left, mid, right, temp) def _merge(arr, left, mid, right, temp): i left j mid 1 k 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 p in range(left, right 1): arr[p] temp[p]你可以看到这份代码的语法结构几乎和 Java 版本一一对应。这里没有用 Python 的切片也没有返回新列表而是直接对原数组进行原地修改。如果你想保留原数组的不可变性可以在入口复制一份再传进去不过那样空间开销会多一截自行取舍即可。4.3 迭代式自底向上归并排序递归的反向视角递归实现是从“大数组拆到小数组”再“从小合并到大”迭代实现则反其道而行之直接把相邻的小段两两合并然后用更大的步长重复这个过程。它的好处是避免递归调用栈深度的问题在一些对栈空间敏感的语言和环境中更安全。迭代归并排序的核心是控制“子数组宽度” width。一开始 width 1把相邻的每两个长度为 1 的数组合并成长度为 2 的有序段然后 width 2把相邻的每两个长度为 2 的有序段合并成长度为 4 的有序段每次宽度翻倍直到宽度大于等于数组长度。Java 的迭代版实现如下public static void mergeSortIterative(int[] arr) { int n arr.length; int[] temp new int[n]; for (int width 1; width n; width * 2) { // 每次处理两个宽度为 width 的子数组 for (int left 0; left n - width; left 2 * width) { int mid left width - 1; int right Math.min(left 2 * width - 1, n - 1); merge(arr, left, mid, right, temp); } } }这里的merge函数可以直接复用递归版里写好的merge(arr, left, mid, right, temp)。需要注意的是边界处理当数组长度不是 2 的整数次幂时最后一组的右边界可能超出数组范围所以用Math.min(left 2 * width - 1, n - 1)把右边界限制在n - 1内。同时内层循环的终止条件是left n - width因为要保证至少存在一个宽度为 width 的右子数组否则当前段的右半部分可能为空也不需要合并。我用一个长度为 7 的数组[7, 3, 9, 1, 5, 2, 8]推演一遍迭代过程width 1合并 (0,1)、(2,3)、(4,5)索引 6 单独剩着得到[3,7,1,9,2,5,8]width 2合并 (0,3)、(4,6)得到[1,3,7,9,2,5,8]width 4合并 (0,6)得到[1,2,3,5,7,8,9]注意看第二轮合并时(4,6) 这个区间实际是右子数组长度只有 2 的“不完整合并”但由于merge函数本身支持长度不同的两个有序区间所以一切正常。迭代版和递归版最终结果完全一致但它的递归深度是 0本质上用双层循环替代了系统递归栈。4.4 两种实现方式的取舍什么时候用递归什么时候用迭代很多初学者会纠结“到底应该学哪种实现”我的观点是优先吃透递归版因为它的思想更接近分治的本质也更容易扩展到其他分治算法比如逆序对计数、归并求区间和。但在生产代码中如果数组规模特别大、系统栈深度有限迭代版会更稳妥。在 Java 中递归调用会占用 JVM 栈帧默认栈深度通常能支撑几千到几万层的递归而归并排序递归深度是 log2 n所以即使 n 达到 10 亿递归深度也才 30 层左右并不需要担心栈溢出。但如果你在 Python 里用递归版需要注意 Python 默认的递归深度限制是 1000虽然 log2 n 很少超过这个值但如果你把递归函数定义得嵌套很深比如每次切片复制又递归还是可能触顶。用迭代版能彻底绕开这个问题。另外从性能上看迭代版少了函数调用的开销但多了一些边界条件的判断整体差距通常不足 10%。不要为了这一点点性能去牺牲代码可读性除非你明确知道自己排序的数据量非常大且频繁调用。5. 归并排序的实战应用不只是“一个排序算法”那么简单5.1 经典问题求解逆序对数量归并排序最著名的“衍生应用”就是求一个数组中的逆序对数量。先定义一下什么是逆序对如果 i j 且 a[i] a[j]那么称 (i, j) 是一个逆序对。比如数组[2, 4, 1, 3]中逆序对有(2,1)、(4,1)、(4,3)共 3 个。为什么归并能算逆序对因为在合并两个有序子数组时当右侧数组的某个元素arr[j]小于左侧数组的当前元素arr[i]时说明arr[j]比左侧数组中从i到mid的所有剩余元素都小。又因为i mid这些元素在原始数组中的位置都在j之前所以它们与arr[j]正好构成逆序对。逆序对数量一次就能累加mid - i 1。下面是在上面归并框架上扩展的逆序对计数代码public class InversionCount { private long count 0; public long countInversions(int[] arr) { if (arr null || arr.length 2) { return 0; } count 0; int[] temp new int[arr.length]; sort(arr, 0, arr.length - 1, temp); return count; } private void sort(int[] arr, int left, int right, int[] temp) { if (left right) { return; } int mid left (right - left) / 2; sort(arr, left, mid, temp); sort(arr, mid 1, right, temp); mergeAndCount(arr, left, mid, right, temp); } private void mergeAndCount(int[] arr, int left, int mid, int right, int[] temp) { int i left; int j mid 1; int k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { // 此时 arr[j] 小于左侧从 i 到 mid 的所有元素 count mid - i 1; temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int p left; p right; p) { arr[p] temp[p]; } } }这个算法的时间复杂度仍然是 O(n log n)比暴力双重循环的 O(n²) 快了一个量级。很多 LeetCode 题比如“计算右侧小于当前元素的个数”都可以用这个思路解只是往往还需要结合树状数组或线段树而归并排序提供了另一种不用高级数据结构的解法。5.2 外部排序内存装不下时归并排序是最常用的策略之一当数据量大于内存容量时直接在内存里调用快排或者堆排是不现实的因为它们要求所有数据都在内存中可访问。这时候“外部排序”出场而归并排序天然适配外部场景。经典的外部排序分两个阶段阶段一把海量数据切分成多个不超过内存容量的小块对每个小块在内存里用任意快速排序排好写回磁盘。每个排好的小块叫做一个“run”。阶段二把这些排好序的小块用“多路归并”的方式合并成一个整体有序的大文件。“多路归并”其实就是归并排序合并步骤的扩展原来只合并两路两个有序数组现在可以同时合并 k 路k 个有序文件。具体做法是维护一个大小为 k 的最小堆每次从堆顶取出最小元素写入输出文件然后从该元素所属的那一路文件中补充读入下一个元素再重新调整堆。这样磁盘 I/O 次数显著减少整体效率远高于两两归并。我在实习时见过一个大数据的排序需求上游日志文件接近 60GB而服务器可用内存只有 8GB。直接全量加载根本不可能最后就是用外部多路归并解决的先把日志切成 200 多个 run然后做 64 路归并整体跑了 20 多分钟。如果用别的方法内存可能直接溢出。这个场景也说明了为什么归并排序并不只是教科书里的玩具——它在工业界确实有不可替代的位置。5.3 链表排序为什么归并排序是链表的最佳方案链表的排序是一个经常被忽略的考点。数组排序常用的快排依赖随机访问下标链表随机访问是 O(n)所以快排在链表上的性能很差堆排需要建堆和下沉操作链表的指针操作也很别扭。而归并排序只需要顺序访问链表节点这恰好是链表的强项。链表的归并排序思路和数组几乎一致先用快慢指针找到链表中点把链表拆成两半递归排序后再合并两个有序链表。合并时只需要调整指针指向不需要额外的临时数组空间空间复杂度可以降到 O(log n)递归栈开销甚至用迭代法可以做到 O(1) 空间。下面给一个 Java 的链表归并排序核心代码public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } } public ListNode sortList(ListNode head) { // 递归终止条件 if (head null || head.next null) { return head; } // 1. 快慢指针找中点 ListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } ListNode mid slow.next; slow.next null; // 切断链表 // 2. 递归排序左右两半 ListNode left sortList(head); ListNode right sortList(mid); // 3. 合并两个有序链表 ListNode dummy new ListNode(0); ListNode cur dummy; while (left ! null right ! null) { if (left.val right.val) { cur.next left; left left.next; } else { cur.next right; right right.next; } cur cur.next; } if (left ! null) { cur.next left; } if (right ! null) { cur.next right; } return dummy.next; }链表归并排序我最想提醒的一个坑是找中点时fast 指针要初始化为head.next而不是head。如果初始化为head在偶数长度链表下找到的中点会偏右一个节点导致拆分不均匀虽然不影响正确性但可能会使递归深度略大于 log n。虽然影响不大但面试时面试官往往盯着这种细节看。5.4 有哪些场景真的不适合归并排序归并排序不是万能的有些场景下它的缺点会放大数据量小且需要极致性能当数组长度只有几十或者几百时插入排序的常数优势和缓存友好性往往比归并排序更好。所以很多语言内置的排序比如 Java 的Arrays.sort会对小数组切换到插入排序。内存极其紧张归并排序需要 O(n) 的额外空间。在嵌入式环境或者超大文件排序的内存受限场景下可能需要使用原地排序算法如堆排序来避免额外内存。数组非常大但键值简单如果只是对基础类型数组排序Java 的Arrays.sort对基础类型会使用双轴快排因为基础类型没有稳定性要求双轴快排常数更小、更快。而归并排序版本一般只用于对象数组排序保证稳定性。6. 归并排序的常见错误排查我踩过的那些坑和调试思路6.1 递归边界写错left right还是left right很多新手写递归版归并排序时会把终止条件写成if (left right) return;而不是if (left right) return;。在大多数情况下这两者等价但如果你传入的区间是空区间比如left right就会出现死循环或者数组越界。什么情况下会出现空区间当调用sort(arr, left, mid, temp)时如果有left mid那就说明这个区间本身不存在。虽然正常的递归路径不会产生这种区间但如果你修改了中点计算方式或者处理某些特殊索引时出错就可能触发。使用作为终止条件相当于多了一层防御。写递归函数时我习惯用“左闭右闭区间 left right退出”这个组合简单、不容易错。6.2 临时数组的拷贝范围写错只拷了一部分数据合并完成后必须把temp[left..right]这段拷贝回arr[left..right]。我见过一个很经典的 bug有人写成for (int p left; p right; p) { arr[p] temp[p]; }没问题。但有人会顺手写成for (int p 0; p temp.length; p)把整个临时数组都拷贝回去。在一开始合并的区间不是从 0 开始时这个错误会导致原数组左侧的值被覆盖成无意义的数据排序结果一塌糊涂。调试这种问题的最佳方式是在merge函数开头和结尾分别打印区间[left, right]内数组的状态看看拷贝前后数据是否一致。如果发现拷贝前后数据不一致问题几乎一定出在索引上。6.3 用 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)这段代码逻辑没错但每一层递归都会创建两个新列表再加上合并时创建的result列表每层会有 3 次列表创建。随着递归往下走内存对象的数目呈“二叉树枝条数”增长垃圾回收压力很大。我实测过在 Python 中对 100 万元素做这种切片归并耗时比索引版归并多了将近一倍内存峰值也高了不少。如果你只是刷题时写个十几万的数据可能感觉不出来但放到服务端批量处理时性能差距就会很明显。所以如果你在用 Python 做生产环境的排序尽量使用索引加临时数组的方式或者直接调用list.sort()——Python 内置排序是 Timsort它是归并排序的改进版针对真实数据做了大量优化。6.4 稳定性被误写破坏等值判断用而不是这是一个很难用肉眼发现、但后果很严重的错误。合并时写if (a[i] a[j])导致相等元素时取右数组的元素表面上排序结果依然是升序数组依然有序但你丢失了稳定性。稳定性丢失的典型场景是“先按主键排序再按次键排序”。比如先按学号升序排了一次再按班号排一次不稳定排序可能让同班学生的学号顺序乱掉。业务同学如果把这种数据展示到页面上看起来就会“莫名其妙地没有按学号排序”。我建议在测试代码里专门构造一组带唯一标识的对象比如同时有 id 和 sortKey 字段排序后再检查 sortKey 相同的对象 id 顺序是否保持原序。回归测试一旦加上这个断言稳定性问题立刻现形。6.5 迭代版归并的边界条件右边界越界、mid 计算错误迭代版最典型的问题出现在数组长度不是 2 的幂时。例如n 9width 4第二轮合并时left 0mid 3right如果直接用left 2 * width - 1 7就是正确的但如果width增大到 8left 0mid 7right 15显然越界了必须用Math.min(..., n - 1)截断。另一个隐藏 bug 是内层循环条件写错。如果写成for (int left 0; left n; left 2 * width)当left n - 1时mid left width - 1可能超出n - 1merge函数直接越界。我自己的习惯是内层循环条件用left n - width因为只有left width还小于 n 才意味着“存在第二个子数组需要合并”。这个条件我已经背下来了建议你也记一下能省掉好多调试时间。7. 进阶优化如何让归并排序更“快、稳、省”7.1 小数组规模切换插入排序利用常数优势归并排序的递归直到子数组长度为 1 才停下来这意味着最底层会执行大量非常短的递归调用。每次函数调用都有开销而且对于长度为 2、4 的小数组合并带来的临时数组操作并不划算。一个成熟的优化是当子数组长度小于某个阈值比如 16 或 32时改用插入排序。为什么是插入排序因为插入排序在近乎有序和小规模数据上表现出色常数极小而且它是原地排序不需要额外空间。可以参考 Java 标准库的做法Arrays.sort在归并排序递归到小数组时也会切到插入排序。阈值选多少合适理论上和机器有关通常 7、16、32 都是常见选择。我做过的简单基准测试中在 10 万到 100 万元素范围内阈值为 16 时性能提升大约在 5%12% 之间。你可以自己测一下不必迷信某个固定值。7.2 检测数组是否已有序提前终止不必要的合并在合并前如果左子数组的最大值已经小于等于右子数组的最小值那么两个子数组合并后本身就是有序的不需要真正执行合并操作。这个检查只需 O(1) 时间却能在数据已经高度有序时省掉大量合并开销if (arr[mid] arr[mid 1]) { // 左半部分最大值不大于右半部分最小值整体已经有序 return; }这个优化对“近似有序”的数据特别有效。比如日志文件按时间戳已经大致有序但偶尔有几条乱序记录这个检查能让你在大量区间直接跳过合并。实际测试中对近乎有序的数组加入这个检查后归并排序的时间可以下降 50% 以上。与此对应的另一个小优化是在递归返回时如果两个子数组都已经有序可以避免拷贝回原数组的循环。但这个优化实现起来稍复杂收益也不如前一个明显我通常不推荐为了这点收益牺牲代码可读性。7.3 Timsort工业级归并排序的集大成者如果你用过 Python 的list.sort()或 Java 的Arrays.sort(Object[])你其实已经接触过归并排序的“进化版本”——Timsort。它由 Tim Peters 在 2002 年为 Python 实现后来被 Java、Android 等广泛采纳。它做的事情很多核心包括检测输入数据中的“run”连续有序段利用这些天然有序的片段减少合并次数。使用二分插入排序处理短 run并按特定规则合并 run保证合并的平衡性。在合并时采用“飞奔模式”galloping mode当一方连续多次获胜时用二分搜索批量迁移元素而不是逐个比较。Timsort 的思想本质上还是“归并”但它对真实数据的适应性更强。正因为归并排序的“分—治—合”框架足够灵活才能衍生出这么强大的变体。所以学归并排序不仅是为了会写那几十行代码更是为了理解这些工业级排序背后的底层逻辑。7.4 多线程归并利用并行归并提升性能归并排序的分治结构让它天然适合并行化。递归的两个子问题之间互相独立可以交给不同的线程或进程同时处理。最基础的并行归并思路是在递归函数里当子数组规模大于某个阈值时用线程池同时提交两个排序任务等两个任务都完成后再执行合并。Java 里可以这样粗粒度地实现public void parallelMergeSort(int[] arr) { int[] temp new int[arr.length]; ForkJoinPool pool new ForkJoinPool(); pool.invoke(new SortTask(arr, 0, arr.length - 1, temp)); } class SortTask extends RecursiveAction { int[] arr; int left, right; int[] temp; SortTask(int[] arr, int left, int right, int[] temp) { this.arr arr; this.left left; this.right right; this.temp temp; } Override protected void compute() { if (right - left 1024) { // 小数组退化为普通归并或插入排序 mergeSortRange(arr, left, right, temp); return; } int mid left (right - left) / 2; SortTask leftTask new SortTask(arr, left, mid, temp); SortTask rightTask new SortTask(arr, mid 1, right, temp); invokeAll(leftTask, rightTask); merge(arr, left, mid, right, temp); } }使用ForkJoinPool和RecursiveAction是 Java 里最贴合分治框架的并行方案。注意阈值不宜太小否则线程创建与上下文切换的开销会吃掉并行收益。我在一个 8 核机器上对 1000 万元素做测试阈值设为 2048 时并行归并大约是单线程归并的 3.5 倍。当然这个倍数和机器核心数、内存带宽强相关你可以把它看作一个数量级的参考。8. 面试和竞赛中关于归并排序的高频题目思路与套路总结8.1 高频题一逆序对数量LeetCode LCR 170这个题目我已经在第 5.1 节给出了完整实现。面试时需要注意不是直接背代码而是要讲清楚“为什么右侧元素入暂时mid - i 1就是新增逆序对数量”。面试官会追问“如果数组中有重复元素你还能用同样的方法吗”答案是能前提是使用arr[i] arr[j]时先取左元素这样统计的是严格大于关系等价于a[i] a[j]的逆序对定义。如果你把条件写成相等元素也会被当作逆序对就错了。8.2 高频题二链表排序LeetCode 148第 5.3 节的sortList就是标准答案。额外要注意的是空间复杂度数组版归并排序的 O(n) 空间在链表上可以省掉因为链表的合并只改指针。面试时能主动点出“链表版不需要额外数组空间”是加分项。8.3 高频题三合并 K 个有序链表 / 数组LeetCode 23这道题本质上是多路归并。最简单、面试也最容易讲清楚的做法是使用最小堆把 K 个链表的当前头节点放入堆每次弹出一个最小值节点把它接入结果链表同时把该节点的后继节点压入堆。堆大小为 K每次操作复杂度 O(log K)总复杂度 O(n log K)。从归并排序的视角看这其实是“K 路归并”这个外部排序核心操作的简化版。如果你已经理解了归并排序的合并在做什么这道题基本上就是“把两个有序数组的合并扩展到 K 个有序链表”。8.4 高频题四区间和的个数LeetCode 327这个题目看起来很吓人但解法核心正是“归并排序 前缀和”。先算出前缀和数组prefix然后问题转化为统计满足lower prefix[j] - prefix[i] upper且i j的前缀和二元组数量。利用归并排序的过程中左右两个子数组内部已经有序可以通过双指针在 O(n) 时间内数出跨两个子数组区间的有效二元组数量。整体复杂度 O(n log n)。我当年刷这道题时把归并排序的merge函数硬是改造成了“归并 统计”的模式改完之后对“归并排序本质上是对有序段做线性扫描”这件事的理解又深了一层。这类题的核心套路就是在合并阶段利用两个子数组已经有序的性质用双指针完成统计而不是去暴力枚举。8.5 面试官真正想考察的点你能不能聊清楚“为什么归并排序是稳定的”面试里围绕归并排序最常见的问题不是“你写个代码”而是“为什么归并排序稳定快排不稳定”这个问题看起来很基础但很多人都答不好。原因在于他们只是记住了结论没理解合并过程中“取左元素”与稳定性的关系。我建议回答的框架是归并排序的稳定性发生在合并阶段。合并时当左右子数组的元素相等时我们规定总是先复制左子数组的元素。左子数组的元素在原始数组中位于右子数组的元素之前因此相等元素的先后顺序得到保留。递归拆分过程本身不改变元素的相对顺序只是切分没有重排所以整体排序是稳定的。快排不稳定则是因为分区操作中基准值的选择和交换可能把相等元素中靠后的元素换到前面。比如经典 Lomuto 分区遍历时遇到比基准小的元素就会与某个位置交换这个位置可能跨越多个相等的元素稳定性自然无法保证。能把这个逻辑链条讲清楚面试官基本就点头了。如果还能补充“Timsort 在 Python 和 Java 中被采用正是因为内置算法需要稳定性”那就更好了。8.6 竞赛中的归并排序变体不只是排序更是数据结构思想在 ACM 或 LeetCode 高阶竞赛里归并排序的“分治框架”可以直接用来做“区间统计类问题”。因为归并排序天然将数组划分成左右两个区间并且当递归返回时左右区间内已经各自满足某种有序性。利用这个有序性可以在合并阶段快速完成跨区间统计。除了逆序对、区间和之外还有“翻转对”LeetCode 493、“计算右侧小于当前元素的个数”LeetCode 315等都可以用归并排序的框架解题。熟练之后你会发现归并排序不仅仅是一个排序工具更是一种在 O(n log n) 时间内处理二维偏序问题的通用框架。这一点可能才是归并排序真正的“高级用法”。9. 从零手写一个属于自己的归并排序推荐的学习路径如果你现在还在“能看懂但写不出来”的阶段我建议按下面的顺序练习每一步都动手敲一遍不要只看不写用伪代码描述合并过程拿一张纸画两个有序数组和一个结果数组用指针模拟整个合并过程直到你不需要思考就能正确“走完”一遍。写一个独立的merge函数输入是left和right两个有序数组输出是一个新的有序数组。这个阶段不涉及递归重点体会双指针线性扫描的机制。你可以用 Python 或者 Java 写跑几个自己构造的测试用例。加入递归把merge嵌入递归框架中处理一个长度为 8 的小数组。打印每一层的left、mid、right以及合并前的左右子数组和合并后的结果对照你手动推演的过程。改成原地版本引入一次性分配的临时数组把“创建新数组”改成“传递索引区间”。这个步骤能帮你理解空间复杂度的优化思路。挑战逆序对计数在原框架基础上增加一个计数变量统计合并阶段的逆序对。当你跑通逆序对计数时你对归并排序的理解就已经远超“会写代码”的层面了。实现链表版本用快慢指针找中点递归排序链表。如果在纸上画链表能画明白链表归并通常一次就能写对。写迭代版本从 width 1 开始两两合并。注意右边界处理。我建议每步都写至少 10 个测试用例包括空数组、单元素数组、逆序数组、全部相等数组、含负数的数组等。排序类算法是最容易“看起来对”但“边界处错得离谱”的多测测试用例比反复抄代码有效得多。另外不要只看我的 Java 和 Python 版本。你可以用自己最熟悉的语言C、Go、Rust、JavaScript各实现一遍重点比较不同语言的索引边界和内存分配习惯这会帮你摆脱“只会在一种语言里写算法”的局限。10. 最后说点我实际使用归并排序的体会从大学第一次接触归并排序到现在我陆续在多个真实项目里用过它日志文件做外部排序、链表数据按时间排序、核心接口里需要稳定排序时手动写一个归并类。每次使用都会重新感叹一次归并排序最大的优点不是快而是“稳定”和“确定”。快指的是最简单直接的时间复杂度 O(n log n)稳定指的是不挑输入数据、性能不会突然崩确定指的是它给了你一条清晰可推导的递归路径无论数据长什么样代码行为都可预期。正因为这种确定性我在写需要长时间稳定运行的服务端代码时如果排序数据的特性不明我会优先考虑归并排序而不是性能上限更高但波动更大的快排。有时候你需要的是一个“不会让你半夜被 oncall 电话叫醒”的算法而不是一个理论性能多 20% 的算法。如果你正在学数据结构与算法请务必把归并排序的拆分、合并、递归、迭代、稳定性、复杂度推导全部吃透。它就像一把万能的钥匙不仅能打开排序的大门还能带你走进逆序对统计、外部排序、链表排序等多扇房间。把这篇文章里的代码自己敲一遍再尝试改造成不同的场景相信你会收获比我文字描述更多的理解。