1. 归并排序到底在解决什么问题1.1 从“两个有序数组合并”说起基础算法集训走到第07天终于碰上了排序算法里“分治思想”的课代表——归并排序。如果你已经学过冒泡、插入、选择这几位“O(n²)家族”成员再看归并排序会有一种豁然开朗的感觉它并不是在原有数组上硬生生地“交换”而是先把问题拆碎再把碎片拼回成有序的整体。先说最简单的引子。假设你手上有两个已经排好序的数组比如A [1, 3, 5]和B [2, 4, 6]让你把它们合并成一个整体有序的数组C你会怎么做最直接的办法是用两个指针分别指向A和B的头部比较当前两个数字哪个小就把哪个放进C然后对应指针后移。这样一路比较下去C天然就是有序的。这个过程叫“二路归并”时间复杂度是O(nm)非常干净。归并排序的核心就是反复利用这件事既然合并两个有序数组很容易那我只要把数组一直对半拆拆到每个子数组只剩一个元素——单个元素天然有序——然后再两两合并就能得到整个有序数组。整个过程没有惊心动魄的交换只有“拆”和“合”两个动作但效果却出奇地稳定。很多初学者第一次看归并排序的代码最大的疑惑就是“它怎么就这么笃定拆开合并后一定是对的”答案就在递归的数学归纳法里只要左右两个子数组各自有序合并出来的数组必然有序而递归的边界是单个元素天然有序于是结论成立。1.2 分治思想的直观理解分治三个字——分、治、合在归并排序里体现得淋漓尽致。“分”就是把原数组从中间切一刀切成左右两半“治”就是对每一半递归地调用归并排序让它们各自变成有序“合”就是把两个有序数组合并成一个。这里没有“治”完就结束最后一步“合”才是归并排序的灵魂。打个生活化的比方假设你负责整理一屋子杂乱的文件。分治的做法是——先把屋子分成两半分别让两个人整理每个整理者又把自己那半再分成两半让更多人来整理直到每个人手里只剩一张纸这张纸不需要整理它已经是最小单元。然后大家两两合并手里的有序小堆每次都按顺序叠好最后全屋子的文件就变成了一摞整整齐齐的有序清单。归并排序的过程就像这个流程只不过“人”是递归函数“纸”是数组元素。对比一下快排快排也是分治但它的核心在“分”也就是partition之后左边都小于pivot右边都大于pivot合起来就是有序的所以快排不需要显式的合并。而归并排序的核心在“合”它的“分”只是简单地劈一半真正的工作量在合并时完成。这个差异决定了归并排序的一个优点它是稳定排序相等元素的相对顺序不会改变。在需要按照多关键字排序时比如先按分数排再按学号排稳定性的价值就体现出来了。2. 归并排序的核心原理与复杂度分析2.1 递归拆分的完整过程我们用一个小数组[38, 27, 43, 3, 9, 82, 10]来走一遍递归全过程。初始时这7个元素是无序的先把数组从中间mid (0 6) / 2 3切开分成左半[38, 27, 43, 3]和右半[9, 82, 10]。然后递归处理左半[38, 27, 43, 3]再切一刀mid 1分成[38, 27]和[43, 3]。再往下切[38, 27]分成[38]和[27]。到这一步两个子数组都只有一个元素递归开始返回。返回时要做合并[38]和[27]合并成[27, 38]。另一路[43]和[3]合并成[3, 43]。然后这两个双元素数组再合并比较过程如下左指针指向27右指针指向33小取出3。左指针还是27右指针指向4327小取出27。剩下左数组空右数组还有43依次放入43。得到[3, 27, 38, 43]。这是整个左半部分的“有序结果”。右半部分[9, 82, 10]同理先切成[9]和[82, 10]后者再切为[82]和[10]合并成[10, 82]再合并最终得到[9, 10, 82]。最后合并左右两个有序数组[3, 27, 38, 43]和[9, 10, 82]得到最终有序数组[3, 9, 10, 27, 38, 43, 82]。整个过程如果你画一棵二叉树会发现递归深度恰好是log₂n量级每一层需要合并的总元素数是n所以总体复杂度是O(n log n)。这个复杂度在日常生活中意味着对1百万元素排序归并排序只需要大约20层递归合并每层处理1百万个元素操作量级在2000万左右而冒泡排序需要约5000亿次比较差距是数量级的。2.2 时间复杂度、空间复杂度与稳定性归并排序的时间复杂度是稳定的O(n log n)无论输入数据是正序、逆序还是完全随机它都表现得一样好。这一点和快排不同快排在极端情况下会退化到O(n²)但归并排序不会因为它总是从中间切分不依赖元素的具体取值。代价就是空间复杂度归并时需要额外开辟一个临时数组来存放合并结果所以空间复杂度是O(n)。如果你使用递归实现递归栈还有O(log n)的额外空间。稳定性方面归并排序是稳定排序。这里的“稳定”指的是如果数组中有两个相等的元素排序后它们的相对顺序不会改变。在合并时我们只有当左半元素小于右半元素时才优先拿左半当两个元素相等时会优先取左半或者保持左半在前的顺序这保证了原数组中先出现的相等元素在结果中仍然先出现。反观快排的partition过程很容易把相等元素的顺序打乱所以快排通常是不稳定的。关于空间很多人纠结“原地归并”的问题。说实话标准的归并排序确实不是原地排序因为合并两个有序数组必须需要一个缓冲区。虽然存在原地归并的技巧比如手摇算法但实现复杂度高、常数大实际工程中并不常用。我们平时说的归并排序默认就是使用额外O(n)空间的标准版本。这也提醒我们在内存紧张的场景比如嵌入式、单片机里归并排序可能不是首选但在地大数据量、需要稳定排序的场景里它的表现非常可靠。3. 代码实现Python / Java / C 三种写法3.1 Python 实现与易错点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) 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 # 把剩余元素一次性加进来 result.extend(left[i:]) result.extend(right[j:]) return result这段代码有几个值得注意的点。第一切片arr[:mid]和arr[mid:]会创建新列表所以这个版本的额外空间不只是O(n)而是O(n log n)因为每一层递归都产生了新列表。对于刷题和教学演示没问题但如果你在做性能敏感的项目最好改写为“原地分割临时数组”的版本只申请一次临时数组。第二比较时用而不是这是为了保持稳定性。如果用相等元素会优先取右半导致原本靠前的相等元素被放到后面去了。第三result.extend(left[i:])这里小心如果i已经等于len(left)left[i:]是空列表extend空列表没有任何副作用所以可以放心写。但如果你在循环里逐个append别忘记处理剩余元素很多人写归并时漏掉这一步导致排序结果缺元素。我再给一个更接近底层实现的版本它直接传入索引区间复用同一个临时数组空间复杂度严格控制在O(n)def merge_sort_inplace(arr, left, right, temp): if right - left 1: return mid (left right) // 2 merge_sort_inplace(arr, left, mid, temp) merge_sort_inplace(arr, mid, right, temp) # 合并 i, j left, mid 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 k in range(left, right): arr[k] temp[k]调用方式merge_sort_inplace(arr, 0, len(arr), [0] * len(arr))。这个版本真正做到了在同一个数组上递归切分合并时用临时数组暂存再拷回原数组。理解它之后你对归并排序的“引用传递”概念会更清楚。3.2 Java 实现与边界处理Java实现通常放在一个类的方法里我推荐下面这种写法public class MergeSort { public static void mergeSort(int[] arr, int left, int right) { if (right - left 1) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid, right); merge(arr, left, mid, right); } private static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left]; int i left, j mid, 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); } }这里最需要小心的是边界定义。我统一采用“左闭右开”的区间写法也就是[left, right)所以初始调用是mergeSort(arr, 0, arr.length)。这种写法在二分、归并、线段树里都非常常见好处是right - left就是区间长度不需要记忆mid该不该加一。mid left (right - left) / 2之所以不用(left right) / 2是为了防止left right整型溢出。虽然现代JVM里数组长度很难达到溢出阈值但这是个好习惯。合并时temp数组长度是right - left每次合并都new一个临时数组频繁分配会有性能开销。你可以把temp作为成员变量一次性分配长度arr.length然后通过索引控制写入位置这样能明显减少GC压力。另外System.arraycopy是一个native方法比手动for循环拷贝快不少。刷题时直接手写for循环没毛病但工程代码里能用arraycopy就用。3.3 C 实现与内存优化C常见的实现有两种一种是直接在原数组上递归合并另一种是配合vector使用。我给出一个兼顾性能和可读性的版本#include vector using namespace std; void merge(vectorint arr, int left, int mid, int right) { vectorint temp(right - left); int i left, j mid, 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]; for (int p 0; p temp.size(); p) { arr[left p] temp[p]; } } void mergeSort(vectorint arr, int left, int right) { if (right - left 1) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid, right); merge(arr, left, mid, right); }如果追求性能可以避免每次merge都构造临时vector而是在mergeSort函数内部维护一个全局临时数组vectorint temp; void mergeSort(vectorint arr, int left, int right) { if (right - left 1) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid, right); int i left, j mid, 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]; for (int p left; p right; p) { arr[p] temp[p]; } }调用前先把temp.resize(arr.size())。这样每次合并只是把数据拷到temp对应位置再拷回来少了很多频繁分配内存的开销。实测对1千万级随机整数排序这种优化大约能带来15%~20%的性能提升主要归功于缓存局部性和避免分配次数。C版还有一个细节如果用vectorint传参一定记得传引用arr否则会发生整个数组的拷贝时间复杂度直接变成O(n²)。新手最容易在这个地方翻车。4. 归并排序的经典应用逆序对问题4.1 问题模型集训第7天如果只讲排序那就太浪费归并排序的潜力了。它有一个非常经典的延伸应用——求逆序对数量。逆序对的定义是对于数组a如果i j且a[i] a[j]那么(i, j)这一对数就是一个逆序对。比如[2, 3, 1]中(2,1)和(3,1)是两个逆序对。这个问题的暴力解法是双层循环时间复杂度O(n²)适合小数据。但数据量一上来比如n10^5暴力就超时了。用归并排序可以在排序过程中顺手统计逆序对的数量时间复杂度保持在O(n log n)。原理是当合并两个有序子数组时如果取右半元素a[j]说明左半中从当前指针i到mid-1的所有元素都比a[j]大它们和a[j]都构成逆序对。所以每取一次右半元素就累加mid - i。4.2 在归并过程中统计逆序对在标准归并代码的基础上只需要加一个计数变量def merge_sort_count(arr, left, right, temp): if right - left 1: return 0 mid (left right) // 2 count 0 count merge_sort_count(arr, left, mid, temp) count merge_sort_count(arr, mid, right, temp) i, j, k left, mid, 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 count mid - i # 关键左半剩余元素都比 arr[j] 大 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 k in range(left, right): arr[k] temp[k] return count注意只有当arr[i] arr[j]时才累加mid - i。如果arr[i] arr[j]不算逆序对所以用作为取左半的条件。这一点在题目要求“严格大于”时尤其重要很多同学一激动直接把写成结果逆序对数量整个算错。我拿[8, 4, 2, 1]测试递归到最小合并左半[8,4]时8比4大取右指针元素4此时mid - i 1累加1合并[2,1]时累加1最后合并[4,8]和[1,2]时取1对应原数组的1累加mid - i 24和8都比1大取2累加24和8都比2大总共11226个逆序对。手动数一下[8,4,2,1]确实有(8,4),(8,2),(8,1),(4,2),(4,1),(2,1)正好6个分毫不差。5. 集训第7天常见问题与排查技巧5.1 递归栈溢出与迭代式归并递归实现虽然逻辑清楚但有一个天然问题当数组长度非常大比如10^8递归深度大约log₂N也就是26左右这个深度对栈并不危险。真正危险的是某些语言里递归调用本身开销大或者你写代码时不慎无限递归。排查递归问题最直接的方法是检查边界条件如果mergeSort的退出条件是right - left 1那么当right - left 2时mid left 1左右子区间长度都是1可以安全退出如果误写成right - left 1长度1的区间也会继续递归永远走不到底栈就爆了。如果担心递归栈深度可以使用迭代式自底向上归并排序。思路是先用步长1把相邻两个元素合并成有序对再用步长2合并相邻两个有序对步长翻倍直到整个数组有序。伪代码如下def merge_sort_iterative(arr): n len(arr) width 1 temp [0] * n while width n: for left in range(0, n, 2 * width): mid min(left width, n) right min(left 2 * width, n) merge(arr, left, mid, right, temp) width * 2迭代式归并没有显式递归每一步都在做同样的事情相邻两个有序块合并。它和递归版的时间复杂度完全一致但编写时对边界条件的要求更高尤其是mid和right不能超过n。我建议初学者先用递归版理解思想等熟练掌握后再看迭代式。5.2 稳定性与指针边界很多人在合并时把边界写拧导致排序结果出现莫名错误。常见错误有三类第一类mid计算偏移错误。如果区间是[left, right)mid应该是left (right - left) // 2而不是(left right) // 2。虽然大多数情况下两者一样但当代数很大的时候(left right)可能溢出。更关键的是如果你用的是闭区间[left, right]mid的语义就变了左右区间分别是[left, mid]和[mid 1, right]。两种区间写法都能写出正确的归并排序但千万不要混用。我见过一个同学在merge函数里用闭区间在sort函数里用开区间结果合并范围对不上数组越界。第二类合并后忘记把temp拷贝回原数组。很多语言里你直接操作的是引用如果merge只把结果写到temp里而原数组没有更新那么上一层递归得到的就是错误数据。每次merge完成后一定要同步原数组。第三类稳定性被破坏。我之前强调过比较时用才能保证稳定性。如果你觉得“用和用差别不大”在逆序对题目里就是天壤之别。养成习惯从左半取数时用这是归并排序稳定性的保证。5.3 归并排序在 LeetCode 和头歌等平台上的刷题建议在线刷题平台上归并排序的直接考查形式不多但有两个方向非常常见一个是直接让你手写排序算法比如LeetCode 912“排序数组”很多解法就是归并排序另一个是逆序对问题比如剑指Offer 51“数组中的逆序对”。此外链表排序也会用到归并思想比如LeetCode 148“排序链表”因为链表无法随机访问快排的partition不适合而归并排序只需要访问头节点和依次后移指针天然适配链表结构。在头歌这类实训平台上归并排序通常是“基础算法”实训单元的一关。操作步骤一般是读取输入数组调用归并排序函数输出排序结果。遇到这类题目注意输入可能有负数、重复元素、极大数组等情况。我的建议是不要只记模板要理解递归树每一层做了什么。面试官或者出题人稍微变一下比如求最小和、区间逆序对、用归并思想求“右侧小于当前元素的个数”本质上都是在merge过程中做统计。你只要抓住“合并两个有序数组时可以边合并边计算数值关系”这一点就能举一反三。我练题时有个习惯把归并排序的合并过程单独抽出来作为一个独立的merge函数来测试。比如先测试两个有序数组合并是否正确再测试残缺边界最后再放到整个排序流程里。这种做法能帮我快速定位问题也推荐给大家。归并排序的代码逻辑并不难难的是边界和细节一旦单独验证了合并函数整个排序算法基本就稳了。另外很多同学纠结“归并排序的空间复杂度是O(n)”担心刷题时内存不够。实际上刷题平台给的内存通常足够容纳一个临时数组。但如果遇到极度苛刻的内存限制可以考虑使用原地归并的变种如手摇归并但那种代码复杂且常数大不建议在集训阶段死磕。先把标准归并写对再逐步优化是更高效的学习路径。最后分享一个小技巧在写归并排序的合并逻辑时用手在纸上画两个有序数组用两个箭头模拟指针移动每次比较和赋值都同步画出来。我当年就是这么学会的。只要你把“取小放前、指针后移、剩余元素拼接”这三步刻在脑子里归并排序就真正成了你的基本功。集训第07天把这个基础算法吃透后面学快排、堆排以及各种进阶分治问题都会顺畅很多。