一口气打通归并排序是我在准备算法面试时做的最值的一件事。归并排序Merge Sort这名字你肯定听过但很多人对它的理解停留在分而治之四个字上真要手写一遍就卡壳递归边界怎么写合并时那个临时数组到底拷不拷回原数组为什么有的写法会死循环这篇文章我打算把归并排序的原理、推导、模板和坑全部揉碎了讲附上Java、Python、C三套可以直接用的算法模板再聊聊面试和工程项目里最常遇到的几个衍生问题。不管是刚学数据结构的新手还是准备笔试面试的同学或者工作中需要自己处理排序逻辑的工程师这篇都适用。1. 归并排序的核心思想分治法的最佳代言1.1 为什么天生就是分而治之归并排序的思路一句话概括把数组从中间一分为二分别排序再把两个已经有序的半边合并成一个完整的有序数组。这句话里藏着三个动作——分、排、合。分是整个流程的第一步也是理解递归的钥匙。你想象自己对着一副乱序扑克牌排序先把牌堆从中间分成两堆每堆再对半分成两堆一直分到每堆只剩一张牌为止。当一堆牌只剩一张时它天然就是有序的不需要任何比较逻辑这就是递归的出口。接下来从最小的一堆牌开始两两合并每次合并都保持有序小堆变成中堆中堆再拼成大堆最后整副牌有序。这个思路妙在它把一个规模为n的问题变成了两个规模为n/2的子问题再把子问题的结果用线性的代价拼装起来。如果你之前接触过递归会发现分——递归——合并是递归处理问题的标准套路。而归并排序是这个套路里最没有变化、最干净的一种实现所以它几乎成了所有算法教材讲解分治法时的第一个案例。为什么要绕这么大一圈去排序直接遍历一遍选最小值不行吗可以但那是选择排序每选一个最小值就要扫描一次剩余部分整体是O(n^2)的代价。归并排序通过递归把问题拆小之后合并操作的代价是线性的数列每一层只需要线性扫描一次整体代价因此被压到了O(n log n)。这一点后面我会专门推导。1.2 起点是合并两个有序数组不管你用哪种语言写归并排序真正干脏活累活的永远是merge合并这个函数。它处理的问题非常纯粹给定两个已经各自有序的数组把它们合并成一个整体有序的数组。合并的思路用双指针可以很自然地描述。假设左边数组叫left右边叫right各自维护一个指针从头开始走。每次比较两个指针指向的元素谁小就把谁先放进结果数组然后对应指针向后挪一位。等某一方的指针把数组走完另一方的剩余元素因为本来就是有序的直接整体接到结果数组尾部。整个过程每个元素只看一次时间复杂度O(nm)其中n和m分别是两个数组的长度。这个操作可以打一个比方两个班级的学生已经各自按身高排好队现在要把两个班合并成一个整体队列进入会场。辅导员的办法绝不是让所有人重新打乱再排一次而是每次只看两个队的队首谁矮谁先出队站到新队列里。两个队首一轮一轮地比新队列自然也就有序了。这个操作很机械没有复杂分支但它的价值恰恰在于稳定和高效。归并排序的整个算法本质上就是不断重复调用这个合并能力先把数组一路拆到单元素再用merge把相邻的有序片段两两拼接回来。理解了merge你就理解了归并排序的一半。这也是我建议初学者第一个要亲手实现的函数就是merge的原因。2. 手把手拆解归并排序全过程从分解到合并2.1 递归分解为什么非要拆到单元素为止用递归实现归并排序代码上通常是一个包含四个区域的函数mergeSort(arr, left, right) { if (left right) return; mid (left right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); }四个区域各司其职if判断是递归出口mid计算是拆分点两次递归调用负责处理左右子数组最后的merge负责把两个有序子数组合并回来。先说出口。当left等于right时当前区间只剩一个元素单个元素天然有序不需要再分所以直接返回。有些写法会在left 1 right时做特殊处理其实没必要统一用left right作为出口最省心代码逻辑也最简单。再说mid的计算。很多教材写的是mid (left right) / 2这在大多数场景下没有问题。但如果你处理的是超大数组left和right都可能接近int类型的上限这时候left right可能溢出算出来的mid变成负数程序直接出bug。稳妥写法是left (right - left) / 2数学上等价但避免了加法溢出。这个细节在笔试和真实工程里都有可能踩到我第一次参加线上笔试就吃过这个亏。递归调用的区间划分也值得留意。左半区间是[left, mid]右半区间是[mid 1, right]这种左闭右闭的写法配合left right的出口整体逻辑非常清晰。初学者容易写错的地方是把右半区间写成[mid, right]导致left和right在某次递归中保持原值形成死循环最后栈溢出。我后面会在模板分析的章节里单独讲这个坑。2.2 合并过程双指针的妙用merge函数是归并排序的核心动作。假设当前要合并的区间是arr[left...right]mid是左右分界点那么左半区间是arr[left...mid]右半区间是arr[mid1...right]它们各自已经有序。合并的目标是把它们按从小到大的顺序重新填回arr[left...right]。合并过程先分配一个临时数组temp长度是right - left 1用来暂存合并结果。然后用三个指针i指向左半区间的起始位置leftj指向右半区间的起始位置mid 1k指向temp数组的当前写入位置0。接下来就是标准双指针流程——不断比较arr[i]和arr[j]谁小就把谁写进temp然后对应指针后移当某一半区间走完另一半剩余的已经有序的元素直接拷贝进temp。等temp装满了当前区间的全部元素最后一次System.arraycopy或memcpy把temp写回arr的[left, right]位置。这一步很多人会忘。如果不拷贝回去那arr在合并后依然是原始乱序整个排序等于白做。记住归并排序的所有合并结果都发生在临时数组里最终必须落回原数组递归上层才能继续使用这个有序结果。有一个细节必须强调比较时用arr[i] arr[j]而不是arr[i] arr[j]。当两个元素相等时优先取左半区间的元素进temp。这个等号归左的约定是归并排序稳定性的唯一来源。如果写成了那么相等元素的相对顺序会被打乱稳定性就被破坏了。后续第5章我会解释稳定性在真实场景里意味着什么。2.3 复杂度分析稳定与代价归并排序的时间复杂度是O(n log n)推导并不复杂。设T(n)表示对n个元素排序的时间那么它等于两个规模为n/2的子问题时间之和再加上合并两个有序子数组的线性时间O(n)于是有递推式T(n) 2T(n/2) O(n)展开这个式子T(n) 2T(n/2) n 2(2T(n/4) n/2) n 4T(n/4) 2n ... 2^k * T(n/2^k) k*n。当n/2^k 1时k log2(n)所以T(n) n * T(1) n * log2(n) O(n log n)。从递归树的角度理解更直观。每次递归都把数组对半拆树的高度是log n层最底层有n个单元素节点。合并时每一层所有节点合并操作加起来的代价都是O(n)因为每个元素在每层最多被比较并移动一次。log n层乘以每层O(n)就是O(n log n)。这个复杂度是稳定的不依赖数据的初始顺序——哪怕数组已经完全有序归并排序依然会做完整的分解和合并。快排最坏是O(n^2)归并没有这个问题这是它最大的魅力之一。空间复杂度的说法偶有分歧。每次merge都会申请一个临时数组如果每次递归都新建总分配量是O(n log n)级别的。但同一时刻递归栈上活动的合并操作只有一条路径所以同时存在的最大临时数组长度不会超过n因此归并排序的空间复杂度是O(n)。这里说的O(n)是额外辅助空间不算递归栈本身的O(log n)。稳定性方面归并排序是稳定排序。稳定性在算法教材里的定义是如果两个元素相等排序后它们的相对顺序和原数组保持一致。这一点在工程里很重要。比如你有一个订单列表先按下单时间排好序再按优先级排序如果排序算法不稳定第二次排序会把第一次的时间顺序打乱导致同一优先级内部时间也是乱的。归并排序因为合并时相等取左的设计天然保持稳定性这也是Java标准库对象排序为什么要用TimSort一种基于归并思想的排序算法而不是快排的原因之一。3. 三种语言的算法模板与代码解读3.1 Java版本模板带详细注释Java或许是面试中最常要求手写的语言之一我给出的模板也是LeetCode题解里最常见的写法。public class MergeSort { 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); } private 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; // temp数组的写入指针 // 双指针合并谁小谁先进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]; } // 把合并后的结果写回原数组 System.arraycopy(temp, 0, arr, left, temp.length); } }这套模板有三个关键点要记住。第一出口判断是left right不是left right这样可以涵盖空数组的边界情况。第二mid用left (right - left) / 2计算防止溢出。第三merge里最后一步System.arraycopy不能省。我见过不少人在白板上写到这里突然忘掉拷贝然后用test case一跑发现数组纹丝不动。如果追求更优的性能可以在一开始就申请一个和arr等长的全局temp数组然后把它作为参数递归传递每次merge直接复用。这样做的好处是避免每层递归都new数组减少GC压力。3.2 Python版本模板Python写归并排序有一种更直观的写法利用切片直接传递子数组省去了left、right这些边界参数。def merge_sort(nums): # 递归出口空列表或单元素列表天然有序 if len(nums) 1: return nums mid len(nums) // 2 # 分治分别排序左半和右半 left merge_sort(nums[:mid]) right merge_sort(nums[mid:]) # 合并两个有序列表 return merge(left, right) def merge(left, right): i j 0 result [] 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 # python列表可以直接extend剩余部分 result.extend(left[i:]) result.extend(right[j:]) return result这种写法的好处是代码极短、可读性极强非常适合快速演示原理。代价是列表切片会生成新的列表频繁切片会额外占用内存空间开销比原地写法大一些。在LeetCode等平台做简单题目时问题不大但如果你在写生产代码或者处理数据量较大的场景我更推荐用基于索引的原地写法哪怕代码丑一点性能会稳妥很多。还有一个小细节merge里result.extend(left[i:])和result.extend(right[j:])会创建切片临时列表。更省内存的做法是用循环逐个append但代码会稍微长一点。衡量下来我平时用extend方案因为可读性好性能差异在大多数场景下可以忽略。3.3 C版本模板C版本和Java版本思路一致不过需要自己管理临时vector。#include vector using namespace std; void merge(vectorint nums, int left, int mid, int right) { vectorint temp; temp.reserve(right - left 1); int i left; int j mid 1; while (i mid j right) { if (nums[i] nums[j]) { temp.push_back(nums[i]); } else { temp.push_back(nums[j]); } } while (i mid) temp.push_back(nums[i]); while (j right) temp.push_back(nums[j]); // 拷贝回原数组 move(temp.begin(), temp.end(), nums.begin() left); } void mergeSort(vectorint nums, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); merge(nums, left, mid, right); }C里要特别注意vector的reserve。如果没有reservepush_back在元素数量较多时会频繁扩容造成不必要的数据拷贝。先reserve(right - left 1)一次性分配合适容量效率会高很多。另外move的作用是把temp中的元素移动回nums而不是拷贝。对于int这种基础类型move和copy没有本质区别但如果vector里存的是复杂对象move可以避免深拷贝开销。考虑到归并排序的辅助数组通常用于存储待排序元素使用move更贴合C的语义习惯。如果你所在的团队要求严格规避using namespace std记得补上std::前缀。3.4 模板中容易写错的三个边界点第一个边界点是mid的区间归属。我见过不少人在手写时把递归拆成mergeSort(arr, left, mid - 1)和mergeSort(arr, mid, right)这种写法在两个元素mid靠左的场景下会出大问题。举个例子left0, right1mid0。左递归区间是[0, -1]直接返回右递归区间是[0, 1]和当前调用完全一样于是无限递归直到栈溢出。根本原因在于区间划分没有严格缩小问题规模。所以统一使用[left, mid]和[mid1, right]是最保险的。第二个边界点是合并结果写回。merge结束之后temp保存着合并后的有序数组此时原数组arr的[left, right]区间还是乱序或半序状态必须写回。我在面试别人时经常看到候选人写完merge就停手觉得temp数组有序了任务完成了但实际上调用方期待的答案是arr本身变得有序temp只是辅助仓库。每次merge结束一定要有一句拷贝动作把结果落回对应位置。第三个边界点是while循环的条件。合并主循环的终止条件是i mid j right也就是两边都还有元素时进行比较。如果有一边已经遍历完剩下的一边就直接进收尾循环。有些初学会写成while (i mid j right)看似差不多但左区间最后一个元素会被漏掉因为i mid时元素arr[mid]还没有被处理。吃透这三个点归并排序手写基本不会出错了。4. 归并排序的应用场景不止是排序4.1 经典应用一求逆序对数量逆序对的定义是对于数组中的两个下标i j如果arr[i] arr[j]那么这一对元素就是一个逆序对。逆序对数量在数据分析、相似度计算等领域都有应用。最朴素的做法是两层循环枚举所有组合O(n^2)的复杂度在数据量上万时就很吃力了。归并排序可以在排序过程中顺带统计逆序对时间复杂度O(n log n)。秘密就在merge函数里当左半区间当前指向的元素arr[i]大于右半区间当前指向的元素arr[j]时因为左半区间内部已经有序所以arr[i]到arr[mid]的所有元素都大于arr[j]它们都会和arr[j]构成逆序对。于是这一下就能累加mid - i 1个逆序对而不是一个。原理并不复杂举个具体例子。左半区间是[3, 6, 8]右半区间是[1, 4, 5]。合并时i指向3j指向13 1那么左半区间的[3, 6, 8]三个元素都大于1逆序对加3接着j移动到4i还指向33 4正常取左当i指向6时6 4左半区间[6, 8]两个元素都大于4逆序对加2。整个统计过程发生在元素被移动进temp的那一刻不会额外增加时间复杂度只是把merge里的else分支稍微改一下。核心代码就是在else分支加一行if (arr[i] arr[j]) { temp[k] arr[i]; } else { count mid - i 1; // 关键一次累加所有和arr[j]构成的逆序对 temp[k] arr[j]; }这道题在很多算法面试中都会出现堪称归并排序的变形题经典。如果你能独立写出带逆序对统计的归并排序面试官对分治和内功的认可度会高不少。4.2 经典应用二链表排序数组版本的归并排序需要O(n)的额外空间原因是合并时需要辅助数组暂存结果。链表的归并排序却可以打破这个限制因为链表节点的移动只需要修改指针完全不需要额外数组。这也是LeetCode第148题排序链表要求用O(n log n)时间、O(1)额外空间实现的基石。链表归并排序的结构和数组版几乎一样唯一区别是找中点的方式。数组通过索引直接取mid链表则需要用快慢指针快指针每次走两步慢指针每次走一步当快指针走到链表末尾时慢指针正好在链表中间位置。合并两个有序链表是链表的经典操作。两个链表的头节点分别用指针维护比较两个头节点的值较小的节点从原链表摘除并接到结果链表尾部直到其中一个链表为空另一个链表直接接入尾部。全程只改变next指针不会创建新节点空间复杂度天然是O(1)。链表归并还有一个额外的好处它是稳定的。数组版的稳定性依赖合并时相等取左的代码约束链表版则天然满足因为合并两个有序链表时你完全控制哪个节点先接出去稳定性的实现成本甚至比数组版更低。4.3 归并排序的变体与优化归并排序并不是一条道走到黑工程上有很多变体让它更实用。第一个变体是小区间插入排序优化。递归分解到子数组长度很小时通常16到32递归调用的函数栈开销可能超过直接排序的成本。这时候可以改用插入排序处理小区间减少递归深度。Java标准库的TimSort本质上就是归并 插入排序的组合优化。第二个变体是外部排序。当数据量大到无法全部载入内存时归并排序几乎是唯一合理的选择。它可以分批把数据读入内存每批排序后写回磁盘形成多个有序片段再用多路归并的方式把所有片段合并成一个完整有序的文件。这个过程中归并排序的顺序读写特性完美匹配磁盘访问模式而快排的随机访问模式在磁盘上会异常低效。大数据领域的很多排序方案底层都是这个思路。第三个变体是交替数组减少拷贝。递归级别的归并排序每次都要把temp拷贝回原数组拷贝开销O(n)被计入每次合并。如果改用两个数组轮流作为读写目标可以减少不必要的拷贝次数。比如第一轮把arr归并到aux第二轮把aux归并回arr交错进行最终的排序结果可以直接落在目标数组上代码逻辑会复杂一些但实际运行时的数据搬移量明显减少。5. 常见问题与排查技巧实录5.1 递归堆栈溢出问题理论上归并排序的递归深度是log nn为100万时深度也就20层不会触及栈上限。但一旦递归边界写错形成死循环栈溢出会来得非常快。排查的思路很简单在mergeSort函数入口打印left和right观察有没有区间和上一次完全相同。如果出现完全相同的情况说明递归区间划分有误大概率是mid的归属或者边界条件写错了。另一个StackOverflow的来源是用Java递归处理超大数组时虽然深度只有几十层但如果虚拟机的线程栈设置得特别小理论上也可能溢出。这种情况较少见真遇到了可以在启动参数里调整-Xss但更根本的做法是检查你的递归有没有多次回溯到同一区间。别问我怎么知道的我曾经在链表归并排序里用快慢指针找中点快指针更新完没有判断null导致递归在单节点链表上反复进入同一状态那次排查花了半个多小时。还有一个小技巧如果你怀疑是栈溢出先用小规模数据比如10个元素测试如果小数据正常放大数据才崩优先考虑是不是有隐藏的无限递归如果小数据就崩直接检查递归出口。5.2 内存占用与空间优化技巧归并排序的空间开销让它在某些场景下不太讨喜。原版每层递归都new一个temp数组虽然峰值空间O(n)但整体分配次数很多。实际优化手段有三招。第一招是复用同一个temp数组。在主函数里一次性申请和原数组等长的temp然后作为参数传入mergeSort和merge每次合并都在temp的[left, right]区间内操作。这样整个排序过程只发生一次数组分配对GC非常友好。第二招是前文说的交替数组法。严格来说它不是在省空间而是在减少拷贝次数。引入两个角色源数组和目标数组。第一轮把arr合并到temp第二轮把temp合并回arr轮流交替最后一次合并的结果直接落在arr上省掉了每次归并后的整段拷贝。第三招是用分块插入排序混合方案。当递归拆分到小块时直接用插入排序排好再往上做归并。这样做既减少了递归次数也能在空间上降低调用栈深度属于工程里最常见的归并排序优化组合。不过话说回来如果内存真的很紧张我自己通常不会强上归并排序而是改选堆排序或改进版快排。归并的强项是稳定和有序数据友好如果这两点不敏感没必要和内存较劲。5.3 笔试/面试中的高频陷阱面试里问归并排序通常不只是让你背代码还会有几个追问点。第一个追问是复杂度推导。你得能当场写出T(n) 2T(n/2) O(n)并展开最好能把递归树画出来。只会背结论不行的面试官换个角度问如果你是数据分布完全逆序归并会比快排差吗你就能根据复杂度公式回答不差归并复杂度固定。第二个追问是稳定性。面试官会问归并排序稳定在哪里如果我把merge里的改成会怎样。这时候要能解释清楚稳定性来源于合并阶段对相等元素的处理策略改成后相等但来自右半区间的元素会被先取走左右半区间的相对顺序就被打破了。第三个追问是变体应用。最常见的两道延伸题是求逆序对和排序链表。这两个问题我在前面已经讲过建议提前写好练熟。它们考察的其实还是对merge和分治的理解而不是背答案。第四个追问是和其他排序的比较。比如归并、快排、堆排序的区别、什么场景下你会选归并而不是快排。典型答案需要稳定性时选归并数组版面对链表选归并数据太大需要外部排序选归并内存极紧张时选堆排序对常数性能敏感且不怕最坏情况可以选优化过的快排。回答时要结合场景说理由不要只背结论。5.4 稳定性、并行化与真实场景选型稳定排序在真实项目中的价值前面用订单排序的例子提过。更具体的场景是SQL里的ORDER BY如果数据库先按A字段排序再按B字段排序一个稳定排序算法可以保证A字段相等的记录保持第一次排好的B字段顺序。许多数据库排序组件对稳定性的要求是硬性的这也是为什么现代编程语言内建的对象排序算法大多采用归并或基于归并的TimSort而不是快排。多核时代下归并排序还有一个常被低估的优势——它天然适合并行化。分治法把数组切成两个独立子问题两个子问题之间没有任何数据依赖完全可以交给两个线程甚至两个计算节点去处理最后只需要一次合并。相比之下快排的partition步骤需要全局数组并行化成本复杂得多。Java的Fork/Join框架就可以非常自然地用归并排序演示分治并行。回到实际选型我个人的经验一句话能用库里排序就用库别自己造轮子。Java的Arrays.sort对基础类型使用双轴快排、对对象使用TimSortPython的sorted底层也是TimSort这些库函数已经结合数据规模和局部性做过大量调优。真正需要手写归并排序的场景是这三类算法面试和竞赛、库函数无法覆盖的定制需求比如逆序对统计、以及超大规模数据的外部排序。掌握归并排序的价值不只是会写这一个算法而是吃透一套分治思维这套思维在后续学CDQ分治、线段树合并、多路归并等问题时都会反复出现。最后分享一点我自己的体会。刚学归并排序那会儿我也觉得它代码又长又要额外内存远不如快排来得爽利。直到做了几次真实项目里的数据排序才慢慢明白稳定、可预测、不受输入数据分布影响这些性质在系统设计里往往比所谓的常数小一点重要得多。如果你正在准备面试或者刚学算法我建议你花一个晚上把三件事做一遍第一不看任何代码自己写一遍merge函数第二用归并排序解一次逆序对和排序链表第三亲手把数组归并改成链表版本。这三步做完你对分治的理解绝对会上一个台阶。