1. 归并排序的定位为什么排序算法里绕不开它我第一次认真琢磨归并排序是被一个面试问题逼的哪种排序最坏情况也能做到 O(n log n)而且还稳定当时我脑子里能想到的排序算法不少但第一反应全是快速排序。快排平均是 O(n log n)最坏却会退化到 O(n²)稳定性也要看具体实现根本不算合格答案。后来我把归并排序从头到尾重新学了一遍才意识到它在排序算法族里的特殊地位最坏 O(n log n)、稳定、实现思路清晰这三点同时满足的经典算法基本就它一个。我会从归并排序的分治原理讲起给出可以直接复制运行的 Java 代码把每一行的含义拆开讲清楚然后推导复杂度、分析稳定性再聊聊我实际写代码时踩过的边界问题最后介绍几个工程上常用的优化手法和衍生应用。无论你是刚学数据结构的学生还是想系统补一遍排序基础的工作党都可以照着步骤慢慢复现。1.1 和常见排序算法的横向对比先把归并排序放进整个排序算法谱系里看它的位置就很清晰了排序算法平均时间复杂度最坏时间复杂度额外空间稳定性冒泡排序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)稳定这张表能读出几个关键信息。第一归并排序是最坏情况有硬保证的无论输入怎么排列它都稳定在 O(n log n)这一点在实时性要求高的场景非常重要。第二它是稳定的而且稳定性不依赖任何复杂的实现技巧只要合并时把相等元素的处理写对稳定性天然成立。第三代价是 O(n) 的辅助空间这也是很多人嫌弃它的理由但这个代价换来的是规律的内存访问模式后面讲外部排序时你会发现这个规律反而是它最大的资产。1.2 什么场景会让你想到归并排序归并排序的出场机会通常不是给一个随机数组排序这种简单任务而是下面这几类数据规模大到内存装不下。归并排序只依赖顺序读取和顺序写入非常适合磁盘、磁带这类顺序访问介质外部排序的底层就是多路归并。需要稳定排序。比如按某个关键字排序时希望保持原有的相对次序归并排序是教科书里唯一能稳定做到 O(n log n) 的通用比较排序。数据结构不是数组而是链表。链表无法随机访问快速排序的性能优势完全发挥不出来而归并排序只要沿着 next 指针走就行配合快慢指针找中点可以轻松实现链表排序。需要统计逆序对数量。归并排序在合并过程中天然可以顺带统计逆序对这是很多算法场景的标准解法。我遇到的大多数人学归并排序都是先从数组版开始我也是。所以下面我先把数组版讲透最后再回头说链表和逆序对的应用。2. 分治思想归并排序背后到底在做什么2.1 把大问题拆成小问题归并排序的核心思想是分治这个词听起来抽象其实概括起来只有三步分解把数组从中间一分为二。解决递归地对左半和右半分别排序。合并把两个已经有序的子数组合并成一个有序的大数组。这个过程很像组织一场淘汰赛先把队伍分成小组小组内部比出名次再让各组的第一名、第二名依次对决最终排出整个赛区的名次。拆到什么时候为止拆到每个子数组只剩一个元素——一个元素天然有序不需要再排。拿 8 个元素的数组举例第一层切成 44第二层切成 2222第三层切成 1 乘 8。整个过程可以画成一棵二叉树每个节点代表一个子数组节点的两个孩子就是它切出来的两半。叶子节点全是单元素数组已经有序然后从叶子开始逐层向上合并每一层把所有节点都合并完整个数组就完全有序了。这棵递归树有多少层从 n 个元素一路切到 1每层减半所以层数是 log₂n。树有 log₂n 层每层要处理的总数据量都是 n所以总工作量是 n 乘 log₂n。这个直观理解比死记 O(n log n) 有用得多后面推导复杂度时还会用到。还有一点值得对比快速排序是先处理、再递归归并排序是先递归到底、再在返回的路上处理。快排在每次递归时都要做分区操作把基准元素放到最终位置归并排序真正干活的是合并这一步所有排序动作都发生在递归返回的途中。2.2 合并操作为什么高效合并两个有序数组本质上是一个拉链过程。想象两条已经排好的队列每次比较队头元素谁小谁出队进入结果队列直到某条队列空了就把另一条队列剩下的元素全部搬过来。这里有个核心结论合并两个长度分别为 m 和 n 的有序数组最坏只需要 m n - 1 次比较。因为每产生一个输出元素至多需要一次比较最后一个元素不用比也知道位置。整个过程每个元素最多被比较一次、被移动一次加上最后把剩余整段搬过去总代价就是两个数组长度之和。这个近乎线性的开销是归并排序整体高效的基石。很多人会问合并时为什么不直接就地交换非要开辅助数组因为要把两个有序片段合到一起同时还要保持 O(n log n) 的复杂度原地做非常困难。经典的原地归并需要复杂的旋转操作代价是常数因子变大甚至在某些实现里会退化成 O(n²)。教材里的归并排序普遍采用辅助数组用空间换时间换来的是简单、可靠、可预测的性能。这个取舍在我多年的工程实践里反复出现代码容易写对往往比省那一点内存更重要。3. Java实现从递归框架到合并核心逐行拆解3.1 接口设计与辅助数组的一次性分配直接上代码。我习惯把对外方法和内部递归方法分开对外方法只负责参数校验和资源准备内部方法专注递归逻辑public class MergeSort { public static void sort(int[] arr) { if (arr null || arr.length 2) { return; } int[] temp new int[arr.length]; sort(arr, temp, 0, arr.length - 1); } private static void sort(int[] arr, int[] temp, int left, int right) { if (left right) { return; } int mid left ((right - left) 1); sort(arr, temp, left, mid); sort(arr, temp, mid 1, right); merge(arr, temp, left, mid, right); } }这里有一个很重要的设计辅助数组 temp 只在 sort 入口分配一次然后一路传下去。刚开始很多学习者会把 temp 写在 merge 方法里每次合并都 new 一个新数组。这样做在小数组上没感觉但数组一大频繁分配和垃圾回收的开销会明显拖慢性能而且这个开销和排序本身是同一数量级的。等做完基准测试你会对分配数组也是成本有切身体会。3.2 递归边界与中点计算递归终止条件是left right。为什么不是left right因为写成是防御性写法即使某次调用传入的参数异常也不会出现死递归。排序的两个子问题分别是[left, mid]和[mid 1, right]中间不会重叠所以正常的递归序列里其实只会出现left right但防御性写法能让代码更稳。中点计算用left ((right - left) 1)而不是(left right) / 2。很多人知道这是为了避免整数溢出但没细想什么时候会溢出。Java 里 int 最大值是 2147483647当数组长度超过这个数的一半时left right就可能超过 int 范围变成负数导致 mid 算错甚至出现死循环。虽然日常很少遇到这么大的数组但这是个习惯问题写成位运算版本既防溢出又顺带做了除以 2 的运算一举两得。3.3 merge方法三个指针的拉链接下来是归并排序的心脏——merge 方法private static void merge(int[] arr, int[] temp, int left, int mid, int right) { 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 { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } System.arraycopy(temp, left, arr, left, right - left 1); } }三个指针的含义要记牢i 指向左半部分当前要比较的元素j 指向右半部分当前要比较的元素k 指向辅助数组 temp 中下一个要写入的位置。初值分别是 left、mid 1、left。第一个 while 是主循环每一轮比较 arr[i] 和 arr[j]把较小的放到 temp[k]然后对应指针前进。这里有个细节当两个元素相等时我们取左边那个而不是这是归并排序稳定性的关键后面我会专门展开。主循环结束后一定有一半还有剩余元素。比如左半全部处理完了右半剩下的一截本身就是有序片段直接整体搬进 temp 即可。两个 while 分别处理左边剩和右边剩两种情况互斥且至少有一个会执行。最后一步是把 temp 中 [left, right] 这段已排好的数据拷回 arr。很多初学者会忘记这一步导致排序结果丢失。记住这条链路排好的数据永远在 temp 里必须 copy 回原数组上一层递归才能继续用。我用一个例子手动跟踪一遍。假设数组是 {38, 27, 43, 3}第一次进入 sort 时 left0, right3, mid1。先排左半 [0,1]也就是 {38, 27}继续切左右各一个元素直接返回然后合并两个单元素得到 {27, 38} 写回原数组。再排右半 [2,3]也就是 {43, 3}同理变成 {3, 43}。最后合并 [0,3]i0 指向 27j2 指向 3k0。3 比 27 小temp[0]3j 移到 327 比 43 小temp[1]27i 移到 138 比 43 小temp[2]38i 移到 2此时 imid退出主循环右边剩一个 43搬进 temp[3]。最后整体拷回得到 {3, 27, 38, 43}。3.4 完整运行示例补一个 main 方法方便直接跑import java.util.Arrays; public class MergeSort { // sort、merge 方法见上方 public static void main(String[] args) { int[] arr {38, 27, 43, 3, 9, 82, 10}; MergeSort.sort(arr); System.out.println(Arrays.toString(arr)); } }输出[3, 9, 10, 27, 38, 43, 82]实际工程里如果要排序对象数组记得加泛型并传入 Comparator原理完全一样只是比较逻辑从arr[i] arr[j]变成comparator.compare(arr[i], arr[j]) 0。4. 复杂度推导与稳定性分析结果背后的逻辑4.1 递推式推导 O(n log n)归并排序的时间复杂度可以用递推式严格推导。设 T(n) 表示对 n 个元素排序的时间那么递归处理两个 n/2 规模的子数组2 × T(n/2)合并两个子数组遍历一遍所有元素代价 O(n)所以有 T(n) 2T(n/2) O(n)。把这个式子一层层展开T(n) 2T(n/2) cn 2(2T(n/4) c(n/2)) cn 4T(n/4) 2cn 4(2T(n/8) c(n/4)) 2cn 8T(n/8) 3cn...推到第 k 层时T(n) 2^k T(n/2^k) k·cn。当 n/2^k 1也就是 k log₂n 时T(n) n·T(1) n·log₂n·c O(n log n)。这个推导揭示了 n log n 的真正来源递归树有 log₂n 层每一层的总工作量都是 O(n)。无论输入怎么排列递归结构都一样、合并代价都一样所以最坏、平均、最好三种情况全是 O(n log n)。相比快速排序依赖基准选得好归并排序的时间复杂度是硬保证不需要任何运气。如果熟悉主定理也可以直接套T(n) 2T(n/2) Θ(n)a2、b2log_b a 1f(n) Θ(n)落在主定理第二种情形结论同样是 Θ(n log n)两种推导殊途同归。4.2 空间复杂度的真实开销归并排序的空间复杂度经常被简单说成 O(n)严谨一点要拆成两部分显式辅助数组长度 n这就是 O(n)。递归调用栈深度 log₂n每层压栈的空间是 O(1)总计 O(log n)。所以严格写是 O(n log n)但 n 主导通常就记作 O(n)。递归栈这部分在大 O 记号里被吞掉了实际中也要注意方向因为递归深度只有 log₂n一般不会栈溢出真正吃内存的是那个和原数组等长的辅助数组。这个 O(n) 的辅助空间在内存紧张或嵌入式环境里是实打实的负担。比如手里只有几十 MB 堆内存要排 10MB 的 int 数组辅助数组又占 10MB加上其他对象内存可能就吃紧了。所以归并排序并不是所有场景的最优解它是一个用空间换时间、用空间换稳定性的典型。真到内存极度受限的场景你会优先考虑堆排序但如果内存够用又要求稳定归并排序就是很省心的选择。4.3 稳定性一个 决定生死稳定性指排序后相等元素的相对顺序保持不变。归并排序的稳定性只取决于合并时的一个判断两个元素相等时先取哪边的。if (arr[i] arr[j]) { // 相等时也取左半保证左半元素在前 temp[k] arr[i]; } else { temp[k] arr[j]; }如果把改成当 arr[i] 和 arr[j] 相等时代码会走 else 分支把右半的元素先放进 temp。原本在左半、位置更靠前的那个元素反而被排到后面去了稳定性就被破坏了。这个细节很容易被忽略因为对纯数值排序来说结果一模一样根本看不出差别。但当你排序的是对象数组比如按成绩排序学生列表两个学生分数相同你希望保持他们在原列表里的先后顺序这时候稳定性就变得非常重要。这种需求在多字段排序时尤其常见先按主字段排再用次字段做稳定排序层层叠加最后得到的数据就符合业务预期。所以我的习惯是只要写比较排序一律用或compareTo 0不给自己留隐患。5. 我踩过的坑归并排序的边界问题与调试经验5.1 中点计算溢出的隐蔽问题前面说了位运算防溢出但还有个更容易踩的坑如果你用的是(left right) / 2在小数组上完全正常代码跑得好好的。等你某天处理超大数据或者 left 和 right 都很大时mid 可能突然变成负数递归瞬间全乱。这个问题的特点是平时正常、极端才炸很难复现也很难排查。所以我建议从一开始就养成写left ((right - left) 1)的习惯这类防御性写法成本极低能省下未来几小时的排查时间。5.2 临时数组分配的两种策略对比临时数组分配有两种常见策略适用场景完全不同策略写法优点缺点一次性分配入口 new 一次递归传递零重复分配性能好代码多一个参数每次合并分配在 merge 里 new实现最简单产生大量临时对象大数组明显变慢初学者用第二种方便理解但一旦数据量上万性能差距立刻显现。我之前做了一组对比测试n 10 万随机数第二种比第一种慢了三倍不止主要时间都耗在数组分配和垃圾回收上。所以进入工程阶段务必改成第一种。如果你所在团队要求严格限定堆内存辅助数组还可以考虑复用同一个数组并在合并时用偏移量管理不过这会牺牲代码可读性一般没必要。5.3 忘记拷回原数组的经典失误还有一个特别经典的错误merge 里把数据都归并到 temp 了但忘了最后的 System.arraycopy。当天的调试画面通常是某一层递归返回值看起来没问题但排完整个数组后结果只有部分有序或者根本没变化。因为每一层递归都在等前一层把结果写回 arr你漏了这一步上一层读到的还是旧数据。我的调试建议是在中间状态打印关键的 left、mid、right 和数组片段别只盯着最终结果。归并排序是递归结构只看最终结果很难定位是哪一层出了问题。我通常会在 merge 前后各加一行日志System.out.println(merge: [ left , mid ] [ (mid 1) , right ]); System.out.println(before: Arrays.toString(Arrays.copyOfRange(arr, left, right 1)));跑一个小数组一眼就能看到每一层合并的输入和输出问题出在哪立马暴露。调试完记得把日志删掉或者用日志框架的 debug 级别控制输出。5.4 递归深度与栈溢出的关系归并排序的递归深度是 log₂n比如一百万个元素只需要 20 层递归通常不用担心栈溢出。但如果递归边界写错比如sort(arr, temp, mid 1, right)误写成sort(arr, temp, mid, right)区间没有缩小就会无限递归最后抛 StackOverflowError。遇到栈溢出别慌先在 sort 方法开头打印 left 和 right。如果发现区间反复出现相同的值边界条件肯定写错了。另外也要区分两种情况栈溢出是因为递归太深这里正常不会发生还是因为递归停不下来这里最可能。定位思路完全不同前者考虑转迭代版后者优先检查终止条件和区间划分。6. 进阶优化从教材代码到工程可用的归并排序6.1 小规模子数组改用插入排序归并排序在小数组上并不划算因为递归到叶子时每个单元素都要做一次函数调用而这些调用本身有开销。工程上常见的优化是当子数组长度小于某个阈值时直接用插入排序不再继续递归。阈值选多少我测试下来 7 到 15 之间差别不大经典实现里常见的是 7。原因是插入排序在近有序和小规模数组上常数极小切换后整体可以省下大约 10%~20% 的时间。代码只需在递归方法开头加一个判断if (right - left 1 7) { insertionSort(arr, left, right); return; }插入排序子方法写起来很简单就是从 left1 到 right 逐个往前插注意这是作用在子数组片段上的起始位置要用 left 而非 0。6.2 跳过已经有序的合并另一个很实用的优化是如果左半部分的最后一个元素已经小于等于右半部分的第一个元素说明整个子数组已经有序不需要做合并。判断条件就一行if (arr[mid] arr[mid 1]) { return; }这个优化对本来就有序或近乎有序的输入特别有效。最极端的例子是输入就是一个排好序的数组每一层递归都能跳过合并归并排序会退化成接近 O(n) 的检查过程。虽然这个优化不能改变最坏复杂度但对实际数据的加速非常可观。加上插入排序阈值和小数组优化归并排序在大部分真实数据上都能跑得相当不错。6.3 自底向上的迭代版避免递归递归版是自顶向下先拆到底再合并。迭代版反过来先合并相邻的单个元素再合并长度为 2 的块再合并长度为 4 的块依次翻倍直到整个数组合并完。它不需要递归没有栈空间理论上更省内存public static void sortBottomUp(int[] arr) { if (arr null || arr.length 2) { return; } int[] temp new int[arr.length]; int n arr.length; for (int width 1; width n; width 1) { for (int i 0; i n; i width 1) { int mid i width - 1; if (mid n - 1) { continue; } int right Math.min(i (width 1) - 1, n - 1); merge(arr, temp, i, mid, right); } } }这里的 merge 方法和递归版共用逻辑不变。外层循环 width 从 1 开始每次翻倍表示当前待合并子块的大小内层循环每次跳 2 × width把相邻的两个 width 大小的块合并。注意最后一个块可能不完整所以用 Math.min 截取 right同时用mid n - 1跳过那些只有一个完整块、没有配对块的情况。我在实际测试中迭代版和递归版性能基本相当迭代版略快一点点省下了递归调用的开销而且完全没有栈溢出的担忧。如果你在做底层工具库迭代版会更稳。7. 归并排序的衍生应用从数组排序到更广的战场7.1 外部排序归并思想在大数据场景的核心地位很多经典排序算法假设数据都在内存里一旦数据量大到只能存在磁盘上快排、堆排序就都不好使了因为它们需要频繁随机访问。磁盘随机访问的代价比顺序访问高出几个数量级这时候归并排序的顺序读写特性就成了决定性优势。外部排序的典型做法是先把大文件切分成若干能装进内存的小块分别排序后写回磁盘再用多路归并把这些有序块合并成一个全局有序的大文件。这里的多路归并是归并排序思想的延伸一次合并 k 个有序流用堆来选出当前最小值一趟就能把 k 个文件并成一个。我当年处理接近内存容量的日志数据时就是用这个思路设计分批排序流程效果非常直观。想深挖的话可以从败者树置换选择排序这些关键词入手它们都是归并思想在大规模数据上的具体落地。7.2 链表归并排序不需要额外数组的稳定排序链表不能随机访问快排在链表上会退化成没有意义的做法。归并排序只需要沿着 next 指针移动天然适合链表。找链表中点用快慢指针一个每次走两步、一个每次走一步快的到末尾时慢的正好在中点。合并两个有序链表也很自然比较两个头节点小的接进结果链表即可不需要任何辅助数组。在在线评测平台刷题时链表的归并排序是最常出现的考察点之一。核心代码骨架如下public ListNode sortList(ListNode head) { if (head null || head.next null) { return head; } 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; ListNode left sortList(head); ListNode right sortList(mid); return mergeTwoLists(left, right); }这里快指针要从 head.next 开始而不是 head否则在链表只有两个节点时会死循环。细节虽小写错一次就得调试半天。mergeTwoLists 就是标准的两个有序链表两指针合并沿着 next 把较小的节点串起来即可。7.3 逆序对计数合并过程顺带统计逆序对的定义是如果 i j 且 arr[i] arr[j]那么 (i, j) 就是一个逆序对。暴力解法是双重循环 O(n²)而归并排序可以在合并时把统计顺手做了整体复杂度降到 O(n log n)。原理很简单合并过程中当右边元素 arr[j] 小于左边当前元素 arr[i] 时说明左半从 i 到 mid 的所有剩余元素都大于 arr[j]这些元素全部和 arr[j] 构成逆序对。于是一次性累加mid - i 1即可} else { temp[k] arr[j]; inversionCount mid - i 1; }把这段逻辑嵌进标准 merge就能在排序的同时统计逆序对数量。我第一次写的时候对这个顺手的统计印象非常深单看代码就一行但背后是整个分治思想的红利——一次合并恰好覆盖了所有跨左右两半的元素比较不重不漏。我在一些离线数据处理任务里就用这个方式分析过数据序列的混乱程度逆序对数量可以当作序列有序性的一个量化指标。归并排序的适用面远不止数组排序这一件事。最后分享一个实操小技巧如果你在写归并排序的递归版本调试时可以在 sort 方法里维护一个 depth 参数打印时按深度缩进对齐递归树的结构就能一目了然。我后面所有分治算法的代码都保留了这个习惯排查起来比满屏打日志高效得多。
