一说排序很多人第一反应是冒泡、快排、堆排。但如果有人问你怎么设计一种算法无论数据已经有序还是完全乱序都能稳定保证 (O(n \log n)) 的时间复杂度而且相同数值的元素相对顺序还不能变这个问题能在几秒内回答出来的人是真的把排序算法吃透过的。答案是归并排序而它背后那套“大事化小、小事化了、最后拼装回去”的思维方式就是分治思想最标准、最清晰的标本。这篇内容我想把分治和归并放到一起讲不是单纯罗列代码而是拆开揉碎分治到底分的是什么、合的时候靠什么保证正确性、复杂度账怎么算、手写时哪里最容易翻车以及逆序对、链表排序、外部排序这些归并思想的实战变形。适合三类人看准备算法面试、正在补数据结构基础、或者写代码时遇到“又要稳定又要高效”的排序场景、想知道背后原理的工程师。1. 归并排序的价值锚点为什么教科书把它放在分治第一课很多教材把归并排序作为分治思想的第一个完整案例不是因为它最简单恰恰因为它把分治的三个阶段——“分解、解决、合并”——体现得最标准、最没有歧义。快排同样用到了分治但快排的分治重心在“分区”这一步合并不需要额外操作反而让初学者很难分清到底哪部分是“分”、哪部分是“治”归并排序就不一样它的合并不是免费的必须亲手实现一个有序数组合并过程这一下就把分治的“合”字落到实处了。1.1 最坏情况下的复杂度承诺先看一个容易被忽略但很关键的事实归并排序的时间复杂度是极少数“言出必行”的排序算法之一。快速排序平均情况也是 (O(n \log n))但遇到某些特殊数据分布时比如一个已经排好序的数组配上一个糟糕的 pivot 选取策略会退化到 (O(n^2))。堆排序虽然最坏情况也是 (O(n \log n))但它是不稳定排序而且实际运行时的缓存局部性很差因为它一直在跳着访问数组下标。归并排序则是把数组从中间一分为二、二分为四……每一层的划分都极其均匀子问题的规模永远是原来的一半不存在“后来的数据刚好让某一边特别大”这种别扭输入所以它的复杂度承诺是最可靠的。这个特性在实际工程里意味着什么意味着你可以放心地把归并排序当做一个“兜底方案”。我早年做数据处理时遇到过一种很刁钻的情况待排序数据几乎是有序的但用递归实现的快排在那种数据上性能异常难看。后来干脆在数据规模较大且不确定分布状态时用归并排序或混合策略跑出来的时间曲线永远是一条稳定的斜线不会再出现让人冒冷汗的卡顿。1.2 稳定性为什么是工程刚需“稳定排序”这个词在刷 LeetCode 的人眼里可能只是概念题但在真实系统里它是硬需求。什么是稳定简单说两个值相等的元素在排序前谁在前排序后谁还是在前。这个性质在多关键字排序里非常有用。举个例子一个用户表先按注册时间升序排好再按会员等级降序排。如果第二次排序用的是稳定算法那么同一个等级的用户内部依然保持着注册时间的先后顺序如果用了不稳定算法前一次的排序结果全被打乱还要想办法加辅助字段或额外处理。归并排序之所以稳定是因为它在合并两个有序子数组时当左半部分的元素等于右半部分元素时永远先把左半部分的元素放进结果数组。就这一个判断条件上的差异决定了整个算法的稳定性。这是归并排序在“稳”这件事上碾压快排、堆排的根本原因。1.3 一份排序算法横向对比表把归并排序放进整个排序家族里看它的生态位会更清晰算法平均时间复杂度最坏时间复杂度空间复杂度稳定性特点冒泡排序(O(n^2))(O(n^2))(O(1))稳定简单但慢快速排序(O(n \log n))(O(n^2))(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)) 的辅助空间。但它的优势是“全都要”时间复杂度假不了、稳定性能保证、访问内存是顺序的对 CPU 缓存非常友好。这也是为什么 Python 和 Java 内置排序的底层用的都不是纯快排而是基于归并思想的 TimSort——这个话题后面单独聊。2. 分治三步走分解、解决、合并的递归实现与图解分治思想本身只有三句话分解把原问题拆成若干个规模更小的子问题解决递归地解决这些子问题直到小到可以直接出结果合并把子问题的解组合成原问题的解。听起来像废话但归并排序是验证这三句话最严格的考试题——因为它的每一步都必须写出真实的代码。2.1 分解递归从哪里开始拆拆数组的操作简单到令人怀疑“取中间位置一刀切两半”。def merge_sort(nums, left, right, temp): if left right: # 区间内没有元素或只有一个元素天然有序 return mid left (right - left) // 2 # 防止 leftright 溢出 merge_sort(nums, left, mid, temp) # 分排序左半部分 merge_sort(nums, mid 1, right, temp) # 分排序右半部分 merge(nums, left, mid, right, temp) # 合把两个有序区间合并这里有个细节值得说。mid的计算我刻意用了left (right - left) // 2而不是(left right) // 2。在 Python 里两者差别不大但在 C 或 Java 里当left right超过int最大值时就会溢出变成一个负数程序直接崩溃。left (right - left) // 2这种写法从数学上等价却永远安全。养成这个习惯在二分查找和一切递归拆分的代码里都能少踩一个大坑。递归的终止条件是left right。为什么不是left right因为当区间长度为 2 时left0, right1, mid0右半部分递归调用是merge_sort(nums, 0, 0, temp)此时left right返回接着调用merge_sort(nums, 1, 1, temp)也返回。那什么时候会出现left right比如区间长度为 0 时merge_sort(nums, 0, -1, temp)这种场景。所以写成是一种防御性的边界处理保证任何非法区间都不会继续递归。2.2 合并双指针像拉链一样咬合合并两个有序数组是归并排序的“心脏”也是分治思想里“合”字的实体呈现。核心技巧就是一个双指针一个指针指向左半部分开头一个指向右半部分开头每次比较两个指针指向的元素把更小的那个放进辅助数组然后指针后移。就像拉链一样两条有序的带子齿对齿一路咬合过去。def merge(nums, left, mid, right, temp): i, j, k left, mid 1, left while i mid and j right: if nums[i] nums[j]: # 注意是 等于号放左边保证稳定性 temp[k] nums[i] i 1 else: temp[k] nums[j] j 1 k 1 while i mid: # 左半部分还有剩余直接全部拷过去 temp[k] nums[i] i 1 k 1 while j right: # 右半部分还有剩余直接全部拷过去 temp[k] nums[j] j 1 k 1 for idx in range(left, right 1): # 把合并结果写回原数组 nums[idx] temp[idx]最后那个for循环很多人会漏掉。辅助数组里存的数据是“排好序的中间结果”如果合并完之后不把它复制回原数组那么上一层的合并操作读到的还是乱序数据整个算法就前功尽弃了。初学者最容易犯的错就在这里merge 写得热闹结果忘了回写程序跑出来一团乱。用一个小例子走一遍合并过程假设要合并的两个有序区间是[1, 3, 5]和[2, 4, 6]比较1和2取1左指针后移比较3和2取2右指针后移比较3和4取3左指针后移比较5和4取4右指针后移比较5和6取5左指针后移左区间耗尽直接把右区间剩下的6依次放入。这个过程的比较次数在最坏情况下是 (mn-1) 次其中 (m) 和 (n) 是两个区间的长度。也就是说合并两个总长度为 (k) 的数组代价是 (O(k))这个线性代价是后续推导复杂度的重要依据。3. 复杂度与空间账本递归树推导和辅助数组开销归并排序为什么是 (O(n \log n))不能光背结论要能推出来。毕竟面试官最爱问的一句话就是“你跟我说说为什么归并排序的时间复杂度是这个数”3.1 递归树推导(O(n \log n)) 是怎么得出来的设输入长度为 (n)整个算法的时间复杂度记为 (T(n))。观察递归过程把长度为 (n) 的数组分成两个长度为 (n/2) 的子数组解决两个子问题各花 (T(n/2))合并两个子数组花 (O(n))。所以递推关系是[ T(n) 2T(n/2) O(n) ]展开来看[ T(n) 2T(n/2) cn ] [ T(n/2) 2T(n/4) c(n/2) ] [ T(n) 4T(n/4) 2cn ]继续展开[ T(n) 8T(n/8) 3cn ]规律已经出来了。当递归到第 (k) 层时[ T(n) 2^k T(n/2^k) k \cdot cn ]递归的终点是子数组长度为 1也就是n/2^k 1解得 (k \log_2 n)。代入[ T(n) n \cdot T(1) cn \log_2 n ]忽略常数结果就是[ T(n) O(n \log n) ]用递归树的方式看更直观第一层有 1 个节点处理规模 (n)代价 (cn)第二层有 2 个节点每个处理规模 (n/2)总代价还是 (cn)第三层 4 个节点每个 (n/4)总代价依然是 (cn)。每一层的总工作量都是 (cn)一共有 (\log_2 n) 层所以总工作量是 (cn \log_2 n)。这个“每层的工作量相等”的现象是归并排序最优雅的地方。3.2 空间开销(O(n)) 辅助数组与递归栈的区分归并排序的空间复杂度是 (O(n))但这里的 (O(n)) 到底花在哪了要算清楚。首先是辅助数组。在经典的递归实现里程序会开辟一个和原数组等长的临时数组temp每次 merge 都往里面写然后回写。这个数组就是 (O(n)) 的空间。有的初学者会在 merge 函数内部new一个新数组那就要小心了每层递归都创建数组虽然同一时间栈上只有一条递归路径在活跃但总空间仍然是一个长度为 (n) 的数组数量级而且频繁内存分配的开销远大于算法本身的耗时。其次是递归调用栈。归并排序的递归深度是 (\log_2 n)因为每次规模砍半。对于 (n 10^6) 的数组递归深度只有大约 20 层栈空间约为 (O(\log n))。在绝大多数语言和环境下这点深度远低于栈溢出阈值。在递归深度这个维度上归并排序比快排安全得多——快排最坏情况下的递归深度可能达到 (n)那时候栈是真的会爆掉的。值得说明的是通常讨论归并排序时说“空间复杂度 (O(n))”指的是辅助数组这一项。(O(\log n)) 的栈空间相比 (O(n)) 可以忽略。3.3 为什么工程排序很少直接用归并既然归并这么可靠为什么 C 标准库的qsort、很多排序框架默认用的是快排而不是归并答案藏在常数项里。虽然渐近复杂度都是 (O(n \log n))但快排的“分区”操作是在原数组上原地完成的数据交换量小常数项非常低而归并排序每一层都要拷贝元素到辅助数组再拷回来元素搬运次数大约是快排的数倍。对内存中的小规模数据来说快排往往跑得更快。但在两种场景下归并排序的重要性就凸显出来了一是数据规模大到内存放不下必须用外部排序二是在链表结构上排序——链表没有随机访问能力快排的 partition 操作在链表上要么失效要么性能暴跌而归并排序天然就是为链表这种只能顺序访问的数据结构准备的。这也是下一部分要展开的思路。4. 从递归到迭代自底向上归并的适配场景递归版的归并排序是“从上往下”先拆到最小再合并回来。还有一种思想完全相反但结果相同的写法——迭代版也叫自底向上归并排序。它不递归直接从长度为 1 的有序区间开始两两合并成长度为 2 的区间再两两合并成长度为 4 的区间……直到整个数组有序。4.1 自底向上的归并排序实现def merge_sort_iter(nums): n len(nums) temp [0] * n width 1 while width n: for left in range(0, n, 2 * width): mid min(left width - 1, n - 1) right min(left 2 * width - 1, n - 1) merge(nums, left, mid, right, temp) width 1 return nums这里的width表示当前每段有序区间的长度。一开始width1每个长度为 1 的区间天然有序第一轮把相邻的两个长度为 1 的区间合并成长度为 2 的有序区间接下来width2把两个长度为 2 的区间合并成长度为 4 的区间width4、width8…… 直到width n整个数组就是一段有序区间。迭代版的优势在于完全没有递归调用的开销也不存在递归栈溢出的风险纯循环结构逻辑上更贴近“合并”这个动作本身。我实测过 Python 里递归版和迭代版的性能数据量在十万这个量级时迭代版往往能快 10% 左右原因主要就是省去了大量函数调用。4.2 迭代版边界的坑迭代版有一处非常容易写错的地方当数组长度不是 2 的整数次幂时怎么确定每一轮的mid和right。举个具体的例子数组长度n 7当前width 4那么第一段是left 0本来完整的话右边界应该是left 2 * width - 1 7但数组下标最大是 6所以必须right min(7, n - 1) 6。同理mid也不能直接写成mid left width - 1因为可能最后一小段不足width个元素需要mid min(left width - 1, n - 1)。这里还有一个更隐蔽的细节当mid被截断之后可能出现mid等于right即“第二段”根本没有元素。此时merge(nums, left, mid, right, temp)的调用中j初始为mid 1大于right第二个 while 循环直接被跳过merge 函数的三个 while 里只有第一个while i mid在跑最后把所有元素原样拷回去。这个操作看似无用但它是安全的不会造成越界或错误排序。4.3 扩展初始归并段思想自底向上的归并逻辑在外部排序中还有更宏大的应用。当内存装不下全部数据时排序被拆成两个阶段第一阶段把大文件切成若干块每块大小以内存能装下为准在内存里排好序后写回磁盘这些排好序的块叫初始归并段第二阶段把所有初始归并段做多路归并每次从多个段中取最小的元素写出最终的排序文件。第二阶段的核心就是归并排序里 merge 操作的多路扩展。这就是为什么我强烈建议把归并排序吃透因为从 LeetCode 到真实的大数据场景归并的思想始终不断出现——从数组到链表从内存到磁盘它有一套完全统一的内核。5. 手写归并排序最容易踩的坑代码实现看起来不到二十行但实际写错的人非常多。我把这些年见到的典型错误集中整理一下每一个都是真实踩过、真实帮人排查过的问题。5.1 辅助数组在 merge 内部反复新建# 错误示范每合并一次就 new 一个数组 def merge(nums, left, mid, right): temp [0] * (right - left 1) # 千万别这么干 ...这样写的后果是内存分配次数成倍增加数据量大一点整个排序就慢得离谱。辅助数组应该只在merge_sort的入口创建一次然后把引用传到每一层合并里。这是归并排序实现中最重要的性能优化点没有之一。5.2 merge 结束后的回写遗漏前面已经强调过合并完不把辅助数组的数据回写到原数组上一层递归读到的数据依然是乱的。这里给出检查方法在 merge 的最后加上一个循环把temp[left..right]复制到nums[left..right]然后递归的上一层一定会用到这个结果。有一种“优化”写法是只在最后一步回写中间过程不回写用交替数组的方式减少赋值。这种做法虽然能省一半拷贝量但代码可读性下降一个档次如果不是对性能极度敏感建议不要这么玩坚持“合并必回写”的原则正确性优先。5.3 稳定性等号到底放哪边if nums[i] nums[j]: # 正确等号放左边 temp[k] nums[i] else: temp[k] nums[j]如果把写成那么当左右两个元素相等时算法会先取右边的元素相等元素的相对顺序就被颠倒了归并排序瞬间从“稳定排序”变成“不稳定排序”。这种 bug 很难被普通测试发现因为大多数排序评测只关心结果是否正确、不关心元素先后位置但只要面试官让你写一个稳定排序而你写成了那就直接翻车了。5.4 迭代版right和mid越界迭代版的边界处理在前面已经详细提过这里再补一个检查用例。建议测试时用n 1、n 2、n 3、n 5、n 7这几组非 2 的幂的长度分别跑一遍。很多时候写迭代版感觉天衣无缝一跑长度为 7 就崩十有八九就是right或mid没有用min()截断。5.5 对空数组和单元素数组的处理def merge_sort(nums, left, right, temp): if left right: return这个终止条件天然覆盖了空数组和单元素数组。但是如果你从merge_sort(nums, 0, len(nums) - 1, temp)入口调用要记得先判断nums is None或len(nums) 2否则会出现left0, right-1的情况mid计算出来是0或负数虽然递归边界能兜住但容易让不熟悉的人疑惑半天。入口健壮性是个小问题却能体现工程师的严谨度。5.6 对小数组过度递归当子数组长度小到一定程度比如 10 到 20 个元素插入排序会比归并排序快很多——因为插入排序没有函数调用和数组拷贝的开销常数极小。TimSort 正是利用了这一点当待排序区间小于某个阈值时直接切换到插入排序当区间较大时才进行归并。实际开发里如果你要造排序轮子不妨也做同样的混合优化在merge_sort里加一个判断if right - left 16: 对该区间直接插入排序; return。这个优化在数组规模大时能带来百分之十几到几十的收益几乎零成本。6. 归并思想的三大实战变形逆序对、链表排序与外部排序归并排序最大的价值其实不在排序本身而在“排序过程中顺手解决其他问题”的能力。下面三个经典场景每一个都直接考察归并思想的迁移应用。6.1 逆序对在合并过程中顺手统计逆序对的定义很简单数组中如果前面一个元素大于后面一个元素就构成一个逆序对。暴力解法是两层循环(O(n^2))。用归并排序可以在 (O(n \log n)) 时间内解决而且思路极其自然当合并左半区间[left, mid]和右半区间[mid1, right]时一旦发现右边区间某个元素nums[j]小于左边区间当前元素nums[i]而左半区间从i到mid的所有元素都大于nums[j]那这些元素和nums[j]全都构成逆序对个数是mid - i 1。def merge_sort_count(nums, left, right, temp): if left right: return 0 mid left (right - left) // 2 count merge_sort_count(nums, left, mid, temp) count merge_sort_count(nums, mid 1, right, temp) i, j, k left, mid 1, left while i mid and j right: if nums[i] nums[j]: temp[k] nums[i] i 1 else: temp[k] nums[j] j 1 count mid - i 1 # 统计逆序对 k 1 while i mid: temp[k] nums[i] i 1 k 1 while j right: temp[k] nums[j] j 1 k 1 for idx in range(left, right 1): nums[idx] temp[idx] return count注意统计放在else分支里也就是发现右边元素更小时一次性把左半区间还没合并的所有元素全部计入。如果放到比较完再循环逐个判断复杂度又变回 (O(n^2)) 了。这个“一次性批量计数”是整道题的题眼。类似的变形题还有“每个数右边有多少个比它小的数”“数组中的最小和”等套路都是同一个在归并的合并阶段做附加统计。6.2 链表版归并排序快慢指针找中点数组版归并排序依赖 O(1) 的下标查找来取中位元素链表没法直接按下标访问怎么办用快慢指针找中点慢指针每次走一步快指针每次走两步当快指针到达末尾时慢指针正好停在链表的中间位置。def sort_list(head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next right_head slow.next slow.next None left sort_list(head) right sort_list(right_head) return merge_lists(left, right) def merge_lists(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next这里有个细节fast初始化为head.next而不是head。如果fast head对于只有两个节点的链表slow也会跑到第二个节点链表就没有被真正分成两半。初始化为head.next是为了让慢指针最终停在靠左半部分的最后一个节点上从而正确切分。这类边界问题手写时非常容易错建议多跑几个链表长度的用例验证。链表版本的价值在于数组归并是稳定排序但需要 O(n) 额外空间而链表归并的合并过程只需要改变指针指向、不需要额外数组是真正意义上的原地归并空间复杂度降到了 O(log n)。能写出链表归并说明你对归并的“合并”这个动作的理解不是靠背代码而是理解了指针是怎么拼接的。6.3 外部排序当内存装不下全部数据时最后一个变形规模更大。假设你有一个 10GB 的日志文件需要按时间排序但内存只有 1GB任何常规排序算法都直接失效。这时候归并排序就是事实上的标准答案思路如下第一步把 10GB 文件分成 10 个 1GB 的块逐块读入内存用内存排序算法快排或归并均可排好序写回磁盘。此时磁盘上有 10 个各自有序的 1GB 小文件这就是初始归并段。第二步同时打开这 10 个文件每次比较各文件当前最小的元素选出全局最小的写入结果文件这个动作重复执行直到所有输入都读完。这就是多路归并。外部排序的难点在第二步如果每次比较都扫描一遍所有归并段的头部那复杂度要乘以归并段数量。工程上会用败者树或堆来维护多路的最小值把每次选取的代价从 O(k) 降到 O(log k)。但无论怎么优化核心骨架依然是我们熟悉的 merge 操作只是从两路变成了多路。这三类变形题本质是同一个抽象在归并过程中利用两个子数组已经有序的事实用双指针一次扫描完成核心工作。掌握了这个抽象逆序对、链表版、多路归并、甚至分布式框架里的 shuffle 阶段都能一眼看穿它们的本质。7. 最后分享一点我练归并排序的经验路径如果你现在正处在学归并的阶段我建议按这个顺序练每一步都在前一步的基础上叠加新的认知第一步先手写递归版数组归并重点体会“分、治、合”三阶段的代码位置直到闭着眼能写出来为止第二步把递归版改成迭代版练习边界处理这会强迫你真正理解每一轮合并的范围第三步写链表版感受不需要随机访问的归并之美第四步用归并解决一道逆序对类的题目把“合并时顺手做附加统计”从技巧变成肌肉记忆。有一个我常年使用的习惯每次写完归并排序自己随机生成几组测试数据包括空数组、单元素数组、全相等数组、逆序数组、随机乱序数组分别跑一遍。全相等数组这一项特别关键它能同时检验稳定性等号方向和边界处理。我见过太多人写的归并排序在普通数据上漂漂亮亮一跑全相等数组就发现顺序已经被打乱了。归并排序是那种“第一眼觉得不过如此越深入越觉得巧妙”的算法。它教会我们的不只是排序本身而是一种极为通用的思维工具面对一个复杂的大问题先想想能不能对半拆开各自解决后再考虑怎么把结果拼起来——很多非排序问题比如最近点对、最大子段和、矩阵乘法里的分块加速全都是这个套路的变体。把归并吃透等于拿到了通向更复杂分治算法的一把通用钥匙。