有段时间我带新人过算法基础几乎每次讲到排序这一章都会有人问同一个问题我已经会写快排了为什么还要单独学归并排序我一般会反问他如果面试官让你手写一个稳定排序并且要求最坏情况下依然是 O(n log n)你第一个想到的是哪个问到这里大多数人就明白了。归并排序原理上不难但要把它写对、把复杂度讲清楚、再迁移到各种面试题里还是有不少门道。这篇文章不打算罗列概念而是会从“合并操作”这个最小单元开始把归并排序拆开揉碎附上 Java 代码、复杂度推导、几个典型扩展场景和调试时容易踩的坑希望对应试数据结构考试、准备算法面试或者单纯想弄懂排序内在逻辑的读者都有帮助。1. 归并排序到底在做什么用“合并”解决“排序”先说一个很多人忽略的事实排序算法之所以不同本质上是对“比较结果”的利用率不同。冒泡排序和选择排序每趟只能确保一个元素到位剩下的比较信息大量被浪费归并排序则不同它把一次比较得到的顺序关系立刻固化成“有序段”再用合并操作把有序段不断拼接变长。想象你手上有两堆已经按顺序叠好的扑克牌想合成一堆有序的牌最直接的办法是什么每次都看两堆顶部的牌取更小的那张放到新牌堆里哪一堆空了就把另一堆剩下的整串接上去。这个操作就是“合并”。它有非常漂亮的特性两个各自有序的序列合并之后依然有序而且整个过程只需要线性时间也就是 O(n) 次比较就能完成。归并排序正是把这个特性用到了极致。对于一个乱序数组你并不直接处理整体而是把数组从中间一分为二。如果左半边有序、右半边也有序那么整个数组的问题立刻变成了“合并”问题。但问题是左半边和右半边一开始并不有序怎么办很简单继续拆。左半边再对半拆右半边再对半拆直到拆出来的每一段只剩下一个元素。一个元素天然有序因为它根本没有第二个元素可以乱。这就是归并排序的完整轮廓对半拆分、递归排序、线性合并。从整体上看它把“排序一个大问题”拆成“排序两个小问题”再加“合并两个有序序列”从局部上看代码结构非常规整没有复杂的交换逻辑只要你把合并函数写对了整个排序就完全正确。这也是数据结构教材普遍把它当作“分治算法”标准案例的原因——归并排序不是用分治思想硬套出来的而是分治策略最顺其自然的产物。你还可以在这里先建立一个纵向的画面递归从上往下拆把数组拆成一堆单元素小段然后从下往上合并两个单元素合并成长度 2 的有序段两个长度 2 的合并成长度 4 的有序段依此类推最后恢复成一个完整有序数组。理解了这条主线后面写递归代码时就不会迷路。2. 合并两个有序数组整个归并排序的核心单元2.1 双指针合并的操作细节合并的前提是左半段 arr[left…mid] 和右半段 arr[mid1…right] 都已经各自有序。合并时使用三个索引i 指向左半段开头j 指向右半段开头k 指向临时数组写入位置。每次比较 arr[i] 和 arr[j]把较小的那个放入临时数组然后对应指针前进一步。某一半先走完时直接把另一半剩余部分全部拷贝过去。这本质上是一个“归并”动作而不是比较排序里的“交换”动作。它最妙的点是两个有序段合并时任何一次比较都能立即确定一个元素的最终归位方向不会出现冒泡排序里那种“今天往右移、明天又往左移”的回退所以整体效率才能稳定在 O(n log n)。public static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left; int j mid 1; int k 0; 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, 0, arr, left, temp.length); }这段代码有几个地方值得细看。第一个 while 的循环条件必须同时满足 i mid 和 j right等于说两边都有元素时才开始正式比较一旦某一边耗尽之后就不需要比较了直接把另一边的剩余段整体接上。最后一步是把临时数组里的内容拷贝回原数组对应的区间这一步最容易漏。2.2 为什么合并过程天然是稳定的稳定排序意味着值相等的元素在排序后保持原有的相对顺序。在合并过程中如果左半段元素等于右半段元素应该先取左边的那个。上面代码里用的是if (arr[i] arr[j])也就是把“小于等于”的情况都归给左边指针。如果把这个条件写成arr[i] arr[j]两个相等元素中右半段的那个反而会先被取走这样左半段原本在前面位置上的元素就被排到了后面稳定性就丢了。所以“使用小于等于”不只是一个代码习惯它直接决定合并操作是否稳定。当前这一步稳定了递归回去的每一层合成都稳定整个归并排序就会稳定这是连锁反应。3. 递归版归并排序拆到单元素再逐层合并3.1 递归拆分的终止条件有了 merge 函数递归版归并排序的骨架很短但信息量不小public static void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); }递归终止条件是left right表示当前区间里要么没有元素要么只有一个元素。一个元素不需要排序直接返回。这个判断比你想象的重要因为如果写成left right虽然能跑过大多数用例但遇到空数组或者处理某些切片边界时left 可能直接大于 right导致递归无法收敛。3.2 合并与递归的搭配执行顺序可以拆解为三条线先一直向左递归到最底部再一直向右递归到最底部然后逐层向上合并。很多人第一次看归并排序代码会觉得奇怪合并不是在递归“之后”才执行吗为什么输出结果看起来像是“先拆完再合并”实际上这是调用栈的自然过程。每一层递归返回后它的左右子树都已经各自有序当前层只需要调用 merge把两个有序子树合并成一个更大的有序区间。这个过程很像二叉树的后序遍历——先处理左子树再处理右子树最后处理当前节点。归并排序的分治递归树也是二叉的所以调用顺序天然就是后序。如果面试官让你画递归树你只需要关注每一层干了什么第 0 层有一个长度为 n 的任务第 1 层有两个长度为 n/2 的任务第 2 层有四个长度为 n/4 的任务直到最后一层全是长度为 1 的任务。每一层所有任务加起来的规模都是 n因此每层总工作量是 O(n)而层数约 log2(n)这其实就是 O(n log n) 复杂度的直观来源。3.3 递归版最容易写错的两处第一处是 mid 的计算。有人习惯写(left right) / 2这在 left 和 right 都很大的时候可能导致整数溢出因为 left right 先相加超过了 int 上限就会变成负数。更稳妥的写法是left (right - left) / 2先做减法再做除法从根本上避免溢出。第二处是递归区间的不一致。mergeSort 的区间是左闭右闭的 [left, right]所以 mid 属于左半部分右半部分从 mid1 开始。合并时左半段是 [left, mid]右半段是 [mid1, right]。只要有一处写成了“mid-1”整个数组就会出现漏排或重复排序的问题。这种错误不会导致程序崩溃但排序结果会非常隐蔽地出错调试起来比报异常还痛苦。4. 时间复杂度与空间复杂度不是背出来的结论4.1 从递推关系推导复杂度很多人能说出归并排序的时间复杂度是 O(n log n)但被问到“为什么”就开始含糊。其实推导很直接。设 T(n) 表示排序 n 个元素所需时间。归并排序把 n 个元素拆成两个规模为 n/2 的子问题所以有 T(n) 2 * T(n/2) O(n)。这个 O(n) 来自合并过程因为两个有序子段合到一起需要线性扫描。把递推式继续展开T(n/2) 2 * T(n/4) O(n/2)代入后得到 T(n) 4 * T(n/4) 2 * O(n/2) O(n)。展开 k 次后第 k 层有 2^k 个子问题每个规模 n/2^k每层总工作量都是 O(n)。当子问题规模缩小到 1 时k log2(n)。所以总复杂度是 O(n) 乘以 log2(n) 层得到 O(n log n)。这个推导过程在面试中经常被考建议每次复习归并排序时都自己推一遍别只记结论。4.2 空间占用超出直觉的部分空间复杂度容易被人低估。归并排序的空间复杂度是 O(n)主要来自临时数组。递归版还需要递归调用栈栈深度是 O(log n)。所以严格来说总空间是 O(n log n)但因为 n 的面积更大一般直接记 O(n)。这里有一个容易被追问的点为什么不采用原地归并把空间压到 O(1)理论上确实存在原地归并算法通过旋转区间或者复杂的交换技巧实现但实现代价很高常数因子也大实际工程里很少用。面试时如果被问“能否优化归并排序的空间”标准回答方向是“可以用迭代版省去递归栈”而不是“实现原地归并”后者性价比太低。4.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)不稳定插入排序O(n²)O(n²)O(1)是冒泡排序O(n²)O(n²)O(1)是注意归并排序在最坏情况下依然是 O(n log n)这是它和快排最本质的差别。快排如果基准选得不好最坏会退化到 O(n²)归并排序不会有这个问题因为它的拆半方式不依赖数据分布每次都是固定从中间切分。代价就是那份 O(n) 的额外空间。5. 稳定排序这层优势为什么库实现偏偏选它5.1 稳定排序的实际含义稳定性这个词面试里十个有八个会问但能把场景说清楚的很少。稳定排序指的不是“排序算法本身稳定高效”而是“值相等的元素在排序后保持原来的相对顺序”。举例有多个学生的记录按学号排列你先按成绩排了一遍再把所有学生按班级排一遍此时希望同一个班里的人仍然保持成绩排序。如果排序算法不稳定第二次按班级排序后成绩顺序就全乱了。归并排序的稳定性来自合并阶段那个“小于等于”的选择。等于时不交换左右顺序等于就保住了前序的相对位置。对基础类型数组来说稳定性没什么存在感因为整型 1 和另一个 1 没有肉眼可辨的差别但对象数组有区别两个对象的某个排序字段相同可能姓名、ID、时间戳都不同这时候稳定性就非常关键。5.2 归并在 Java 类库里的位置Java 的 Arrays.sort 是很多人体会稳定排序最直接的例子。Java 对基本类型数组使用的排序算法主要是双轴快排对对象数组则使用稳定的归并类算法比如 TimSort。TimSort 是归并排序和插入排序的结合体它对现实数据里常见的连续有序片段非常敏感能直接利用这些天然有序段因此实际性能很好。如果你去看 Java 官方文档会发现它对对象数组排序有一条明确保证排序是稳定的。为什么基本类型用快排、对象类型用归并类算法因为基本类型的“相等”是值相等排序后交换了两个相等值也看不出来对象的相等可能只是某个字段相同稳定排序能保证先按字段 A 排好序的记录再按字段 B 排序时字段 A 的顺序能尽量保留。库设计者做这种取舍不是因为快排慢而是因为稳定性对对象排序有实际意义。5.3 稳定性在工程里面的意义工程里稳定排序最常见的应用场景就是多关键字排序。例如电商后台先按销量排序再按评价数排序又比如表格数据支持用户点击多个列头进行排序每点一列前一次排序的顺序就需要被保留。如果底层是不稳定排序点第二列之后第一列的顺序彻底乱套用户会投诉。解决这种问题当然也可以用“比较器里拼多关键字”的方案但很多时候数据源已经按某个字段排好序了你只需要在另一个字段上做稳定二次排序。这时归并排序提供的稳定性比它 O(n log n) 的时间复杂度更让人觉得安心。6. 迭代版归并排序自底向上的另一种写法6.1 循环代替递归的动机递归版很容易看懂但有两个实际隐患。第一递归调用栈深度虽然只有 O(log n)但每一次函数调用都有开销数据量稍微大一点性能就能感知到差异。第二在面试、算法题里有时候环境限制递归深度或者题目要求不能使用递归这时候迭代版就派上用场。迭代版的思想是自底向上从一开始就假设数组被拆成长度为 1 的若干小段然后不断把相邻的段合并段的大小按 1、2、4、8 这样翻倍直到整个数组被合并成一个完整有序段。它本质上是把递归树从叶子开始模拟一遍但不需要真正递归。6.2 自底向上归并的代码public static void mergeSortIterative(int[] arr) { int n arr.length; int[] temp new int[n]; for (int size 1; size n; size * 2) { for (int left 0; left n - size; left 2 * size) { int mid left size - 1; int right Math.min(left 2 * size - 1, n - 1); merge(arr, left, mid, right); } } }这里 merge 函数和递归版用的是同一个只是参数外部循环不断变化。size 表示当前每个待合并小段的长度初始为 1下一轮就是 2、4、8…… 内层循环每次跳 2 * size因为每组合并会处理两个相邻段。有一处很重要right 不能直接写成left 2 * size - 1因为数组末尾可能凑不满一组。如果数组长度是 10前面几次 size 比较小的时候没问题但到最后一段可能只剩一个光杆强行取 right 就会数组越界。Math.min(...)就是为了兜住末尾不足的情况。6.3 迭代版的边界规律迭代版还有一个隐蔽点外层循环条件是size n不是size n。你可以想想当 size 已经等于或超过 n 时说明整个数组已经有序没必要再合并。而内层循环条件是left n - size这个限制确保左边这段至少和右边段一样大否则就不存在成对的合并对象了。如果你在 LeetCode 或其他刷题网站上写迭代版强烈建议用几个不同长度的数组测试尤其是长度 0、1、2、3、4、5、8、9 这种边界值。很多递归版能跑通的代码迭代版会在边界上栽跟头原因就在于那些size和left的判断条件没有覆盖末尾不完整段。7. 从逆序对到链表和外部排序归并的分治扩展7.1 在合并过程中顺带统计逆序对有一道高频面试题给定无序数组求逆序对数量。逆序对定义是 i j 且 arr[i] arr[j] 的数对。直接两重循环是 O(n²)数据大了肯定超时。用归并排序可以把复杂度降到 O(n log n)因为合并过程天然给了你统计的机会。看合并代码的第二个分支当arr[j]比arr[i]小说明右半段的当前元素要和左半段所有的剩余元素都构成逆序对。因为左半段是有序的arr[i…mid]都大于arr[j]所以逆序对数可以一次性加上mid - i 1而不是一个个数。int invCount 0; // 在 merge 的 else 分支里 } else { temp[k] arr[j]; invCount mid - i 1; }这个技巧其实是归并排序最漂亮的扩展之一。面试时如果先让你写归并排序再追问“你能用刚才的框架解决逆序对吗”基本就是在考察你有没有真正理解合并过程中指针移动的含义。平时练题时多想一想“指针每移动一次背后的信息量是什么”就不难顺下来。7.2 链表排序归并的空间优势更明显对数组来说归并排序需要 O(n) 辅助空间但如果是单向链表情况就反转了链表本身没有随机访问能力快排那种依赖随机访问基准定位的算法很难施展而归并排序只需要调整指针不需要额外分配大块内存去存储元素复制。链表归并排序的套路是用快慢指针找到中间节点把链表拆成两段分别递归排序然后按值大小依次把节点串起来。空间复杂度只剩递归栈 O(log n)。这个题目在算法面试中出现频率极高建议手写一遍。你还会发现快慢指针找中点的代码本身又是一道经典题两块内容连着练收益很高。7.3 外部排序与磁盘寻道逻辑当数据量大到内存放不下排序动作就不能全在内存里完成这时归并排序几乎是唯一可行的大方向。做法通常是把大文件切成若干能够加载进内存的块分别排序后写回磁盘然后再用“多路归并”把这些有序文件合并成一个大文件。外部排序之所以爱用归并是因为合并过程可以流式处理只需要在每一路有序文件中维护一个缓冲区每次比较各路当前最小的元素取走后再从对应文件补充。它不要求所有数据同时在内存里这和归并排序“把两个有序流合在一起”的本性完全契合。很多数据库底层的排序实现、大数据框架里的 Shuffle Sort也和这个思路相通。8. 调试归并排序时最容易被坑的几个细节8.1 每次递归都 new 临时数组性能崩了我见过不少归并排序实现merge 函数里每次都new int[right - left 1]。功能没错但性能非常差。归并排序总共有 O(n log n) 次合并操作准确说递归调用了 n-1 次 merge但数据拷贝总量是 O(n log n)。如果每次都重新分配数组JVM 会频繁创建和回收对象造成大量内存分配开销。更稳的做法是在外层只分配一次临时数组然后把它当成参数传给 merge。这样所有递归层级复用同一个数组只使用它的某一段区间。临时数组大小不需要每次都匹配当前区间只要不小于原数组长度就行。这个方法能显著减少运行时间的常数因子。8.2 合并完忘记把结果拷回原数组另一个高频 bug 是把临时数组合并得很整齐但忘了写最后的拷贝步骤。结果就是递归返回后原数组还是乱序的或者只改了一部分。拷回时要注意起点不能总是从 0 开始往 arr 里复制应该从 left 开始长度是 right - left 1。更通用的是循环拷贝for (int t 0; t temp.length; t) { arr[left t] temp[t]; }面试手写时这一步最好在编码前就规划清楚不要在写完 merge 后才发现原数组根本没变。8.3 迭代版右边界越界问题迭代版中right Math.min(left 2 * size - 1, n - 1)不是可有可无的防御代码而是必须逻辑。比如数组长度 5size4 合并最后一次时left0mid3right 如果直接取 7 就越界了。实际只有 0 到 4 个元素右半段只有下标 4 一个元素。少了Math.min程序会因为 ArrayIndexOutOfBoundsException 直接崩溃或者更糟读到脏数据。同样要注意 mid 的取值。迭代版里mid left size - 1这段区间是“左段”的末尾。如果left size已经超过 n说明这段长度已经小于 size本轮它可能没有合并对象内层循环条件会把它过滤掉。8.4 面试和刷题时的几条建议第一手写归并排序前先和面试官确认区间闭开。有人习惯左闭右闭 [left, right]有人习惯左闭右开 [left, right)这两种习惯写出的递归边界不一样自我介绍时先讲清楚后面代码才有依据。第二时间允许的情况下可以把递归版和迭代版都写一遍。面试官看一眼就能判断你是背代码还是真懂因为迭代版的边界处理是背不出来的只能靠理解。第三被追问“为什么归并排序适合排序链表”时重点说链表不需要随机访问和额外数组空间而不是笼统地说“归并排序复杂度低”。复杂度低只是结果关键是要讲出“链表和归并的操作模型相性配”这层因果关系。我自己的体会是归并排序是算法面试里性价比极高的一道热身题。它一不靠技巧堆砌二不靠临场抖机灵只需要你把“合并两个有序段”这个基本动作吃透再把递归拆分的区间关系理清楚代码就能稳稳写出来。每次准备面试前我都会把递归版和迭代版各自白板默写一遍再把逆序对那层扩展想清楚做完这三步数据结构排序这一块的基本盘就守住了。