1. 别只在考卷上见过它归并排序到底厉害在哪不管是期末考试、考研复习还是面试手撕算法归并排序Merge Sort都是绕不开的一座山。很多同学学完冒泡、选择、插入这新手三件套之后自信心爆棚觉得排序也不过如此结果一到归并排序就卡住了。这也不能全怪大家因为归并排序确实是第一个需要你彻底转变思维的排序算法——前面的简单排序都是在一个数组内部原地折腾而归并排序要求你把问题拆开、各自解决、再拼回去这套分而治之的思路是全新的。我见过太多人背了两三天归并排序的代码考试能默写但一问你为什么这个算法的时间复杂度稳定在O(n log n)、为什么必须用额外数组、为什么要先递归再合并就答不上来了。这种状态很危险因为考试和面试最擅长用一两道变体题来检验你是不是真的理解了原理。比如让你用归并排序求逆序对数量比如让你用O(1)空间的思路改写链表归并排序你要是只背了代码遇到这些基本束手无策。这篇东西我打算把归并排序掰开揉碎了讲清楚先讲分治思想再给完整C/C代码并逐段解读然后把时间复杂度和空间复杂度推导一遍接着把它和快速排序、堆排序、插入排序放在一起做选型对比最后聊几个实际应用场景和我在写代码过程中踩过、也见别人踩过的坑。无论你是刚开始学数据结构的本科低年级学生还是正在备战考研、准备面试的进阶选手这篇文章都值得你耐心看完。保证没有废话全部是能直接用起来的东西。2. 分而治之到底是怎么治的二路归并的核心思想拆解2.1 一个朴素问题两堆已经排好序的牌怎么合成一堆有序牌要理解归并排序先别急着看代码先想一个更简单的场景。假设你手上有两摞扑克牌左边这摞从小到大排好了右边这摞也从小到大排好了现在你要把它们合成一摞仍然从小到大有序。你会怎么做正常人都会这么做同时看两摞最上面的那张牌谁小就把谁拿出来放到新的一摞上然后继续比较。如果某一摞空了就把另一摞剩下的牌直接倒上去。这个过程就是二路归并——注意二路这两个字它的意思是一次合并两个有序序列这也是归并排序名称的由来。这个朴素操作有一个非常重要的性质它不需要像插入排序那样在数组里频繁移动元素只需要依次比较、依次放入临时空间整个过程的比较次数在最坏情况下也就是两个序列长度之和减一。这一点在后面分析复杂度时会派上大用场。2.2 递归的魔法把大问题一步步切成小到不能再小现在回到排序问题。一个完整的无序数组怎么用上面的两路归并来排核心思路是分而治之拆成三步分解Divide把当前数组从中间切成两半。解决Conquer递归地对左右两个子数组分别做归并排序。当子数组只剩一个元素时它天然就是有序的递归结束。合并Combine把两个已经有序的子数组合并成一个完整的有序数组。这里的巧妙之处在于即使你完全不去管怎么把子数组排好这个问题的细节只要假设递归能帮你把左右两边排好剩下的事情就只是那个朴素的扑克牌合并操作。整个算法最核心、也最容易被忽略的一点是——合并操作发生在递归返回的过程中而不是深入到底之后再一次性解决所有问题。我举个具体例子。假设数组是[38, 27, 43, 3, 9, 82, 10]归并排序的执行过程是这样的分成[38, 27, 43, 3]和[9, 82, 10]左边继续分成[38, 27]和[43, 3][38, 27]再分成[38]和[27]这两个只有一个元素天然有序开始合并得到[27, 38]同理[43, 3]分成[43]和[3]合并得到[3, 43]合并[27, 38]和[3, 43]比较两个序列的头部3 拿走27 拿走38 拿走43 拿走得到[3, 27, 38, 43]右半部分同理得到[9, 10, 82]最后合并[3, 27, 38, 43]和[9, 10, 82]得到最终的[3, 9, 10, 27, 38, 43, 82]这个过程中每一次合并操作处理的都是两个已经有序的序列。你可以把整个递归过程想象成一场淘汰赛最底层是单个选手每一轮比赛把相邻的胜者合并成更大的胜者直到决出总冠军。2.3 二路这个限定词为什么重要严格地说归并排序并不只有二路这一种形态还有三路归并、多路归并外部排序里经常用到。但教材里默认说归并排序时指的就是二路归并。二路归并的递归树是一棵标准的二叉树每一层把规模折半所以递归深度是 log₂n 级别的。这对于理解它的时间、空间复杂度都至关重要。如果改成三路归并递归深度会变成 log₃n理论上更浅但每一层的合并逻辑变复杂实际性能并不一定更好。我在研究外部排序时试过用多路归并处理几百GB的数据文件当时用的是败者树配合多路归并来减少磁盘I/O那个多路跟这里的二路是同一个思路的延伸——二路是基础理解了二路后面学多路归并和外部排序会轻松很多。3. 手把手实现C/C版本二路归并排序的完整解读3.1 从合并函数写起merge是全部基本功要写归并排序我建议你先单独把merge函数写明白、写熟练。这个函数的作用是给定一个数组arr以及两个相邻的有序区间[left, mid]和[mid1, right]把这两个区间合并成一个有序的大区间[left, right]。void merge(vectorint arr, int left, int mid, int right) { // 1. 申请一个临时数组长度为当前要合并的区间长度 vectorint temp(right - left 1); int i left; // 左半部分的起始位置 int j mid 1; // 右半部分的起始位置 int k 0; // 临时数组的当前位置 // 2. 双指针依次比较把小的先放入临时数组 while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } // 3. 如果左半部分还有剩余直接拷贝 while (i mid) { temp[k] arr[i]; } // 4. 如果右半部分还有剩余直接拷贝 while (j right) { temp[k] arr[j]; } // 5. 把临时数组的结果拷贝回原数组 for (int p 0; p temp.size(); p) { arr[left p] temp[p]; } }这里有几个细节敲代码的时候必须刻在脑子里。第一个细节为什么比较条件写成arr[i] arr[j]而不是这直接关系到排序的稳定性。如果两个元素相等的时候把右边的先放进临时数组那么等值元素的相对顺序就被打乱了。写成意味着左边相等元素优先进入结果这样就保证了值相同的元素在排序后仍然保持原有的相对次序。不过我需要提醒你这个代码里我用的是int数组和的差别确实只在稳定性的语义层面。但如果你把同样的逻辑迁移到结构体数组、对象数组的排序上这个细节就是生死线——比如你按分数排序学生分数相同的时候还希望学号小的排在前面这时候稳定性就直接决定了结果对不对。第二个细节为什么最后必须把临时数组拷贝回原数组。很多初学者会问返回临时数组不就行了吗问题在于merge函数处理的是一个更大递归调用链的中间环节上一层合并操作要在当前区间的结果基础上继续比较。如果当前层的合并结果只留在一个局部临时数组里递归返回后原数组对应区间还是乱序的上一层就没法继续了。所以合并完成之后数据必须落回原数组这句话请你在写每一版代码时都默念一遍。第三个细节临时数组的创建位置。上面的代码在每个merge函数内部都vectorint temp(right - left 1)这在功能上完全没问题但性能上不是最优的后面讲优化的时候我详细说。3.2 递归框架mergeSort的整体调度有了merge递归框架就非常简单void mergeSort(vectorint 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); // 合并两半 }调用入口是mergeSort(arr, 0, arr.size() - 1)。这里值得单独解释一下mid的计算方式。可能你见过有些书上写int mid (left right) / 2这写法在数学上没问题但在编程里有一个隐患如果left和right都接近int类型的上限left right会整数溢出。用left (right - left) / 2就彻底避免了这个问题。在LeetCode上刷题多了你会看到几乎所有标准答案的二分查找、归并排序都是用这种方式算mid的这不是炫技是防爆。代码逻辑本身没什么玄妙的但我在给别人讲的时候多次强调过一个理解窍门不要试图跟踪每一层递归的完整执行细节那样你会把自己绕晕。正确的理解方式是递归信仰——假设mergeSort(arr, left, mid)返回后[left, mid]区间就已经有序了假设mergeSort(arr, mid1, right)返回后[mid1, right]区间也已经有序了。你只需要相信这两个假设剩下的问题就是合并两个有序数组这个简单任务。这就是分治思想的精髓把大问题分到足够小小到可以假设别人已经帮我解决了我只关心合并这一件事。3.3 一趟归并非递归思路帮你把脉络看得更清楚递归版本是主流教材的讲法但如果你觉得递归调用太抽象或者担心递归栈溢出还有一个非常经典的迭代实现思路。它不需要递归而是从步长出发自底向上地合并void mergeSortIterative(vectorint arr) { int n arr.size(); // len 表示当前要合并的子数组长度1, 2, 4, 8, ... for (int len 1; len n; len * 2) { for (int i 0; i n - len; i 2 * len) { int left i; int mid i len - 1; int right min(i 2 * len - 1, n - 1); merge(arr, left, mid, right); } } }这段代码的核心是外层循环的len。初始len 1把每个长度为1的子数组两两合并成长度2的有序数组然后len 2把每个长度2的有序子数组合并成长度4的有序数组以此类推。内层循环的i每次跳到下一个长度为2*len的块然后对块内的两半做一次合并。这个迭代版本有个特别实用的价值考试中经常问你归并排序做了几趟归并或者某一趟归并后的序列是什么样子这个时候你脑子里如果只装着递归代码是画不出来过程的。但是用自底向上的len视角一趟就是len的一轮循环整个过程清清楚楚第1趟合并后所有长度为2的子数组有序第2趟后长度为4的子数组有序以此类推总共需要⌈log₂n⌉趟。我一直建议想真正学懂归并排序的人两个版本都写一遍。写递归版本能帮你理解分治和函数调用栈写迭代版本能帮你把握归并的整体过程和趟数这个概念。两者互相补充缺一不可。4. 复杂度到底怎么算时间、空间、稳定性的完整推导4.1 时间复杂度为什么稳定在O(n log n)归并排序的时间复杂度推导可以说是分治算法复杂度分析的入门范本。假设排序长度为n的数组需要时间T(n)那么它由三部分组成排序左半边T(n/2)排序右半边T(n/2)合并两个有序数组遍历一遍比较加拷贝用时O(n)于是得到递推公式T(n) 2T(n/2) O(n)再加上递归出口T(1) O(1)。这个递推公式可以用两种方式求解。方式一展开法代换法。把公式一层层展开T(n) 2T(n/2) n 2(2T(n/4) n/2) n 4T(n/4) 2n 8T(n/8) 3n... 2^k T(n/2^k) k·n当n/2^k 1时k log₂n于是T(n) n·T(1) n·log₂n O(n log n)。方式二递归树视角。把每一层递归做的事画出来第一层做一次规模为n的合并时间n第二层做两次规模为n/2的合并时间也是n第三层四次规模n/4的合并时间还是n……每一层的总工作量都是O(n)而递归树的高度是log₂n层所以总时间就是O(n log n)。这里面最值得强调的是每一层工作量相同这个事实。为什么快排平均也能到O(n log n)但最坏会退化到O(n²)因为快排的划分可能极度不平衡递归树的每一层工作量不均等。而归并排序每次都是严格对半分递归树永远是平衡的这从结构上就保证了无论输入数据长什么样时间一定是稳定的O(n log n)不存在快排那种最坏情况。4.2 空间复杂度O(n)是不是归并排序的致命伤归并排序的空间复杂度由两部分组成。第一部分是递归调用栈。递归深度是log₂n层每层保存常数级别的状态信息所以栈空间是O(log n)。对大多数现代计算机来说n即使到百万级别log₂n也就20左右栈空间压力很小。第二部分是合并时的辅助数组。这里有个常见的理解误区很多人以为只需要开一个大小为n的临时数组所以空间复杂度是O(n)。其实从严格意义上讲在递归版本的执行过程中每一层不同的merge调用会在不同时刻申请不同大小的临时数组但它们不会同时存在——同一时刻栈上活跃的merge调用中临时数组总大小加起来是O(n)级别的。所以无论你怎么算辅助空间上界就是O(n)。这和快速排序、堆排序的O(1)额外空间快排算上递归栈是O(log n)相比确实是短板。这也是归并排序在实际应用中被动辄上百GB数据量的场景排斥的原因。不过换个角度看这个短板换来了两个不可替代的优点稳定和对数据的访问模式友好。后面讲外部排序的时候你会看到O(n)的辅助空间根本不是问题因为数据量大到根本无法全部载入内存时任何排序都要借助磁盘I/O归并排序的顺序访问模式恰恰最适合磁盘。4.3 稳定性结论为什么相等元素不会乱序排序算法的稳定性定义是如果两个相等的元素在排序前的相对顺序是A在前B在后排序后仍然是A在前B在后那这个排序就是稳定的。归并排序的稳定性在merge函数那里就已经决定了。回顾代码双指针比较时我们写的是if (arr[i] arr[j])也就是左边区间的当前元素不大于右边区间的当前元素时先取左边。这样当相等的元素出现在左右两个区间里时左边那个也就是原始顺序靠前的那个会先被放进临时数组保证了相对顺序不变。这个性质在实践中有多重要我举一个我实际遇到的例子。当年在做一个报表系统的时候需要先按部门分组组内再按销售额排序。我第一反应是用排序把这两个字段做复合排序主关键词是部门次关键词是销售额。但如果用的排序算法不稳定第二字段排完序之后第一字段的组内顺序就会被破坏整个分组排序就废了。最后我选了稳定排序一次解决。类似场景在数据库查询优化、基数排序的每一轮中都会遇到这就是为什么归并排序虽然空间上不占优势但地位仍然不可撼动。5. 选型对比归并、快排、堆排、插入到底该选谁学了那么多排序算法最怕的就是学一个忘一个考试的时候全混在一起。我把归并排序和其他几个主流排序放在一个表里把关键维度都列出来算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序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)稳定归并 vs 快排这两个是面试里最常被要求对比的一对。快排的优势是原地排序、空间占用小、常数因子小所以绝大多数场景下实际跑得比归并快但快排的致命弱点是当输入基本有序或者每次划分选到极端的基准值时会退化成O(n²)。归并排序没有这个弱点无论输入多坏它的时间都是稳定的O(n log n)。所以在面试中如果面试官问你如果要排序的数据非常庞大但无法整体载入内存你选什么正确答案就是归并排序的思路——外部排序就是基于归并的。归并 vs 堆排堆排序时间稳定在O(n log n)空间是O(1)看起来全面优于归并实际上不是。堆排序有一个隐藏的问题它的访问模式是跳跃式的每次从堆顶取最大/最小然后调整堆时要访问堆底元素这导致它的缓存命中率极低在现代CPU架构下实际性能反而不如归并。而且堆排序不稳定。归并排序访问数组是顺序的缓存非常友好。很多系统库里的高性能排序比如TimSort宁可牺牲空间选择归并也不选堆排就是看中它的顺序访问特性。归并 vs 插入插入排序时间复杂度O(n²)看似被完爆但它在n很小比如小于几十的时候常数因子极小实际速度反而比归并快得多。因此很多工程实现会在归并排序的递归最底层设置一个阈值当子数组长度小于这个值时改用插入排序。JDK里的Arrays.sort对对象数组用的TimSort就是这么干的。实际选型建议如果是考研、期末考试的代码题老老实实写归并排序它结构最清晰如果面试问实现一个排序优先回答快排但主动提快排的退化问题如果面试官追问要稳定排序怎么办接上归并如果明确要求空间O(1)只能上堆排或原地快排变体。没有最好的排序只有最合适的排序这句话真的不是空话每个算法都有自己的生存空间。6. 归并排序的三大实战场景逆序对、链表排序、外部排序6.1 求逆序对归并排序最经典的变体题这道题在LeetCode是第493题/剑指Offer第51题几乎每年考研复试和校招笔试都会出现。问题是给一个数组求其中逆序对的总数。所谓逆序对就是满足i j且nums[i] nums[j]的(i, j)数量对。暴力解法是两层循环O(n²)n到十万级别就完全跑不动了。归并排序解法是O(n log n)思路极其巧妙在merge的过程中顺带统计逆序对数量。具体来说当merge函数在比较左右两个有序子区间时如果发现左边的当前元素arr[i]大于右边的当前元素arr[j]那么左区间从i到mid的所有元素都比arr[j]大这一下就产生了mid - i 1个逆序对。把它们全部累加到计数变量里即可。long long mergeCount(vectorint arr, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, k 0; long long count 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { 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 0; p temp.size(); p) { arr[left p] temp[p]; } return count; }我强烈建议你亲手在纸上模拟一遍这个过程。比如数组[2, 4, 3, 1]第一轮归并后左区间[2, 4]、右区间[1, 3]。合并时发现2 1此时左区间的i是0mid是1所以mid - i 1 2说明1和左区间的2、4都形成逆序对一次记2个。等你整个算法跑完逆序对总数是3而数组中确实是 (2,1)、(4,3)、(4,1) 这3对。这道题告诉我们一个重要的方法论很多看起来和排序没关系的统计问题本质上是在考察某个有序性程度而归并排序天然地在递归过程中比较了所有跨区间的元素对所以能顺带完成统计。学会这个思路之后你再看区间和的个数这类变体题目会感觉亲切很多。6.2 链表排序为什么归并是链表最理想的排序算法数组归并需要O(n)辅助空间是因为我们要把合并结果放进临时数组再拷回去。但链表不一样——链表的节点之间通过指针连接合并两个有序链表时只需要调整指针的指向不需要任何额外的存储空间。我记得第一次在公司代码里看到链表排序用的就是归并时还愣了下后来自己想通了链表不支持随机访问快排定位基准值需要来回移动指针性能很差堆排需要数组的下标来维护堆结构链表更玩不转。而归并排序只需要对链表做切分和合并切分可以用快慢指针合并可以用双指针穿针引线每一步都是O(1)空间完成。核心思路分三步用快慢指针找中间节点把链表一分为二。快指针每次走两步慢指针每次走一步快指针到尾部时慢指针正好在中间。递归排序左右两个子链表。用合并两个有序链表的方式把两个有序链表合并成一个。这个合并过程只需要一个哨兵dummy节点依次比较两个链表头结点谁小就接谁全程O(1)额外空间。链表归并排序的空间复杂度严格来说是O(log n)——递归栈还是需要空间的但相比于数组的O(n)已经是非常大的提升。如果你对C不熟、平时写Java或者Go多一点建议用自己熟悉的语言把数组版和链表版各写一遍写完这两个版本之后你对数据结构的物理存储方式如何影响算法设计这回事会有质的理解。6.3 外部排序几十GB文件怎么排归并是唯一的答案这是归并排序真正不可替代的主战场。当数据量大到无法全部载入内存时内存排序算法都失效了唯一有效的办法就是外部排序而外部排序的底层正是归并思想。回到刚才说过的场景假设你有一个20GB的文本文件每一行是一个整数内存只有512MB怎么排序教科书标准做法分两阶段阶段一生成初始归并段run。每次从大文件中读入512MB数据在内存里用快排或者归并排好然后写回磁盘成为一个独立的有序子文件。这样一个20GB的文件大约被切分成40个有序段。阶段二多路归并。把这40个有序段每个打开一个文件指针或者缓冲流同时读出每个段当前最小的元素在它们之间选出全局最小写入输出文件然后从被选中的那个段继续读下一个元素。这个从多个有序序列中不断选最小的过程就是多路归并。如果是二路的话就是每次合并两个段40个段需要合并约6趟如果能开40路同时归并一趟就搞定。第二阶段中在内存里选当前最小的元素用到的数据结构是败者树或者堆这也是为什么你学完堆排序之后再来学外部排序会觉得格外丝滑的原因。整个计算机领域的知识就是这样一环扣一环归并排序的二路虽然简单但它是一切复杂归并方案的基石理解了这个最简单的雏形后面学多路归并、败者树、置换选择排序都是一通百通。6.4 编程语言标准库里的归并痕迹如果前面这些场景还不够说明归并排序的重要性那再举一个每天都用得上的证据编程语言的标准库排序函数。Java的Arrays.sort()对对象数组使用TimSort这个算法的本质是插入排序归并排序的混合体。它会把数组先切成一个个小段run每段用插入排序排好然后用类似于归并的方式把所有段合并成一个大有序数组。Python的sorted()底层也是TimSort。C标准库里的std::stable_sort()要求保持相等元素的相对顺序而标准实现正是归并排序的变体。也就是说你以为归并排序只是考试卷上的一道题但实际上你每天写代码都在间接使用它。理解了归并的原理你才能理解为什么Arrays.sort()对基本类型用双轴快排、对引用类型却用TimSort——基本类型排序不需要考虑稳定性快排更快引用类型可能后面有别的依赖要保证稳定只能用归并系算法。这些细节面试官稍微一追问就能看出你是不是真的理解。7. 实战优化与常见坑从能跑到跑得快7.1 优化一小规模子数组转用插入排序前面提到过归并排序递归到很底层时子数组长度可能只有几个元素这时候递归调用和合并操作的函数调用开销已经超过了直接排序的开销。插入排序虽然时间复杂度是O(n²)但在n小于某个阈值比如16或32时它的常数因子极小实际速度反而更快。工程实现里常见这样写void mergeSortOptimized(vectorint arr, int left, int right) { if (right - left 16) { insertionSort(arr, left, right); return; } int mid left (right - left) / 2; mergeSortOptimized(arr, left, mid); mergeSortOptimized(arr, mid 1, right); merge(arr, left, mid, right); }这个优化看着不起眼但在大型排序中能提升10%-20%的性能JDK里的Arrays.sort也是这么干的。阈值需要根据实际环境调优16到32之间是常见值太大反而会因为插入排序O(n²)的本质拖慢速度。7.2 优化二复用同一个临时数组我在最开始的代码里每次merge都新建一个vectorint temp(right-left1)这在n很大时会导致大量内存申请和释放成为性能瓶颈。一个常见的优化方式是在mergeSort入口处一次性申请一个和原数组等长的临时数组然后把它一路传给merge函数使用void mergeSortWithTemp(vectorint arr, vectorint temp, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSortWithTemp(arr, temp, left, mid); mergeSortWithTemp(arr, temp, mid 1, right); int i left, j mid 1, k left; while (i mid j right) { temp[k] arr[i] arr[j] ? arr[i] : 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]; } }注意优化后的写法有一点不同temp的下标不再从0开始而是直接从left开始方便最后按同样的下标拷贝回原数组。这个微调能减少很多无效的索引变换而且能保证merge内层循环只操作临时数组中本次合并真正用到的区域不会反复申请释放内存。7.3 优化三提前判断是否需要合并有一个非常容易被忽视的优化点如果左区间的最大值小于等于右区间的最小值那么整个区间已经天然有序不需要做合并操作。在merge函数开头加一个判断if (arr[mid] arr[mid 1]) { return; // 两个区间接起来已经有序跳过合并 }这个优化在处理基本有序的输入时效果拔群能让归并排序在最好情况下退化到接近O(n)的时间只需要递归地检查不需要真正合并。从实际工程角度看数据很多时候不是完全随机的而是带一定有序性的这个提前返回的判断能省下大量无谓的内存拷贝和比较操作。7.4 常见坑盘点这几条我踩过也看别人踩过坑一递归出口写成left right。看起来是对的但如果传入的区间本身是空的比如left right就会导致无限递归或者越界访问。建议一律写成left right安全起见。坑二merge时把比较条件里的相等情况处理错了。前面强调过是稳定性的保证。如果不小心写成虽然排序结果在纯数值数组上看起来完全一样但一旦排序对象是结构体数组稳定性就被破坏了。考试题里也经常在这里设坑一定要警惕。坑三临时数组的索引不统一导致数据混乱。我见过很多同学的代码merge函数前面几个循环用temp[k]最后拷贝回去却写成arr[left k]此时k已经是临时数组的总长度再拿它去做偏移就是数组越界。正确的做法是拷贝时用一个独立的循环变量从0遍历到数组末尾或者保证k在拷贝前归零。这类索引混乱问题在写归并排序时特别容易出现建议写完代码后立刻做一次空数组、单元素、双元素、逆序数组、重复元素数组五连测试。坑四递归深度过大导致栈溢出。虽然归并排序的递归深度只有log₂n但如果你把递归出口设得过于宽松比如允许排序长度为10万的子数组继续向下递归而不提前切换成插入排序极端的输入也不会爆栈但每一层的函数调用和临时数组开销会很高。实际工程中如果必须处理超大规模数据建议改用前面讲过的迭代版本彻底消除递归栈的风险。7.5 测试自己的代码五组必跑的用例写完归并排序后我建议你不管时间多紧都跑一下这五组用例空数组[]测试边界处理递归出口必须正确返回。单元素数组[42]最基本的边界。完全逆序数组[5, 4, 3, 2, 1]最能检验排序正确性的一组也是归并排序最不怵的情况。包含大量重复值的数组[2, 2, 2, 2, 2]验证稳定性相关代码不会崩溃同时检查相等值处理逻辑。长度极大的数组比如100万加一个小技巧用rand()生成数据排完序后写一个isSorted函数做校验同时记录时间验证性能量级。这五组跑完代码基本可以放心去考试或者上线。我见过太多人在LeetCode上提交归并排序觉得通过了就万事大吉其实LeetCode的测试用例已经帮你把边界测过了但如果你是在自己工程里用建议还是老老实实补上这几组。最后分享一点点我的个人建议归并排序是我当年学数据结构时第一个被震撼到的算法。从冒泡、选择那种裸的比较交换突然跳到分而治之那种思维方式的转变我现在还记得——原来排序还可以这样玩。后来学快排、学堆排、学外部排序每一次回头看归并都会对它的设计有新的理解。如果你现在正在为期末考试或者考研复习发愁我给你的建议是别急着背代码先用一副扑克牌、几张纸手动模拟一遍归并排序的完整过程。当你亲手把两沓有序的牌合成一沓有序的牌当你亲眼看着递归树一层层展开又重新合并成一棵有序树你就再也不会忘掉这个算法了。之后再动手写代码你会发现一切都顺理成章。代码写完之后再回头理解复杂度推导理解稳定性理解什么时候该用归并、什么时候该选快排——到这一步归并排序这一章你就真的过关了。