经常有人问我分治和归并到底是两个东西还是一个东西。我的回答是它们是一对黄金搭档。分治是方法论解决问题时把大任务拆成小任务再把小任务的结果汇总成大结果归并是这场拆解之后最经典的合并动作把两个有序序列合成一个有序序列。如果你正在学算法或者刷题时被一堆“递归爆栈”“指针越界”折磨这篇文章就是写给你看的。我会从分治的底层逻辑讲起接着把归并排序的代码彻底拆透再顺手解决几个高频经典问题最后分享一些进阶玩法和踩坑实录。所有代码用C写牵扯到复杂度推导的地方我会算给你看。文章不会太长篇大论讲废话该给代码给代码该给经验给经验。1. 分治思想的底层逻辑不是简单的“拆了再合”1.1 分治的核心三件套分治思想听起来玄乎本质上就三步分解、解决、合并。把原来规模为 n 的问题拆成若干个规模更小的同类子问题子问题继续递归拆直到小到可以直接解决然后逐层返回把子问题的解合并成原问题的解。我习惯用一个生活例子来解释。假设你要在一堆扑克牌里找出最大的那一张正常思路是拿着一张一张比O(n) 次比较就结束了。分治的思路是把这堆牌从中间分成两堆分别找出两堆各自的最大牌再比较这两张谁更大。你可能会觉得这不是多此一举吗但注意当“找出最大值”升级成“给整副牌排序”或者“统计多少对元素是逆序的”单次遍历解决不了分治的价值就体现出来了。分治真正厉害的地方不在“拆”而在“合”。很多新手只把分治理解成递归 折半然后写出来的代码只是形式上的分治合并阶段没有任何信息利用那自然快不起来。归并排序的合并阶段利用了“两个子数组已经有序”这个已知条件才能在 O(n) 时间内把两个 n/2 规模的子数组合并成有序数组从而把整体复杂度做到 O(n log n)。1.2 为什么分治能跑得比暴力快这里不得不做一点简单的复杂度推导。以归并排序为例设 T(n) 是排序 n 个元素所需时间递归地看T(n) 2T(n/2) O(n)意思是排序 n 个元素分解成两个 n/2 规模的子问题各花 T(n/2)合并两个有序数组要花 O(n)。展开这个递推式每一层总的比较工作量都是 O(n)递归深度一共 log2(n) 层所以 T(n) O(n log n)。对比冒泡排序和插入排序的 O(n²)n 从 10 万到 100 万规模时O(n log n) 和 O(n²) 的差距不是一倍两倍而是千倍万倍。你想想如果核心业务接口里有一段 O(n²) 的排序逻辑数据一涨接口就超时换成归并或快排瓶颈往往立刻消失。主定理把这些规律总结成了公式。形如 T(n) aT(n/b) O(n^d) 的递推式满足条件时复杂度可以直接查表得出。分治算法的场景非常多归并排序、快速排序、最近点对、快速幂、归并求逆序对核心都是这套“分解-解决-合并”的思路。我踩过的一个坑是分治的子问题必须互相独立合并代价必须可控。如果子问题之间有大量重叠强行分治只会浪费递归开销这时候应该用动态规划或记忆化搜索。反过来如果合并操作本身就需要 O(n²)那整体复杂度还会被合并拖累分治的收益也会被抵消。2. 归并排序最标准的分治实战2.1 核心代码逐行拆解归并排序是分治思想最朴素的实现。我先把完整代码贴出来再逐段讲为什么这样写。#include bits/stdc.h using namespace std; void merge(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; // 左半部分起点 int j mid 1; // 右半部分起点 int 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 idx left; idx right; idx) { arr[idx] temp[idx]; } } void mergeSort(vectorint arr, int left, int right, vectorint temp) { if (left right) { return; // 单个元素已经有序 } int mid left ((right - left) 1); // 防溢出写法 mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); }递归的边界是left right。当区间里只有一个元素或没有元素时它天然有序不需要继续拆。mid的计算我特意用了left ((right - left) 1)而不是(left right) 1主要防止 left 和 right 都很大时整数溢出。虽然刷题时数据范围可能到不了那个量级但好习惯要养起来。合并函数的核心是两个指针 i 和 j分别指向左右两个子数组的当前元素。谁小就先把谁放进临时数组然后对应指针往后走。这个“双指针归并”的手法值得背下来后面求逆序对、求小和问题全都还会用到它。2.2 稳定性与空间占用归并排序是稳定的排序算法这一点和快速排序不一样。代码里我用的是if (arr[i] arr[j])当左右两个元素相等时优先取左半边的元素放进临时数组。因为左半边的元素在原数组中本来就出现在右半边之前这样做保证了相等元素的相对顺序不变。空间占用方面合并时需要一块长度等于当前区间的临时数组。我是在函数外预先分配好一整块temp长度和原数组一样每次合并都复用这块空间。这样做的原因是如果每次递归都在函数内部新建临时数组总的空间开销会变成 O(n log n)而且频繁分配内存带来的常数时间非常可观。实测下来大数据量下每次分配临时数组的版本可能慢上三四倍。时间上归并排序的 O(n log n) 是稳定可预期的不依赖输入数据的初始状态。这一点比快排更让人安心快排在极端情况下会退化到 O(n²)而归并永远不会。2.3 归并排序的应用边界归并排序有一个优势场景常常被忽略链表排序。数组版的归并需要额外临时数组但链表版的归并不需要额外空间只要改指针就能完成合并空间复杂度直接降到 O(1)。LeetCode 上一堆链表排序题用归并几乎是常规解法。数组场景里如果数据量不大、对稳定性没有特殊要求大多数时候直接用内置 sort快排 插入排序混合就够了常数小、代码简单。但一旦遇到“不仅排序还需要在排序过程中统计信息”的问题比如逆序对、小和问题归并排序就是唯一能同时完成排序和统计的选择。这类问题我在下一节详细展开。3. 分治经典问题进阶从排序到统计3.1 分治法求最大元素位置先看一个很多人刷题时遇到的第一关分治法求一个 n 元素数组中最大元素的位置。很多在线实验平台把这道题放在“分治”第一关因为它逻辑简单、结构清晰。int getMaxIndex(vectorint arr, int left, int right) { if (left right) { return left; // 只剩一个元素它自己就是最大值 } int mid left ((right - left) 1); int leftMaxIdx getMaxIndex(arr, left, mid); int rightMaxIdx getMaxIndex(arr, mid 1, right); // 合并比较左右两个最大值返回较大的下标 if (arr[leftMaxIdx] arr[rightMaxIdx]) { return leftMaxIdx; } return rightMaxIdx; }注意几点。第一题目要求返回位置所以我返回的是下标不是值。第二多个最大值同时存在时我用了保证返回的是“第一个”最大元素的位置这是很多题目隐含的细节要求。第三这个算法的时间复杂度是 O(n)因为每一层合并只做一次比较但递归压栈的深度是 O(log n)也算顺带复习了递归。有一点我必须说清楚真正在工程环境中找最大值位置线性扫描就够了几行代码搞定int maxPos 0; for (int i 1; i n; i) { if (arr[i] arr[maxPos]) maxPos i; }分治版的意义在于教学。它能帮你熟练“把大区间拆成两个小子区间再合并子区间结果”的模式为后面更复杂的分治问题打基础。别把精力浪费在纠结“为什么不用遍历”上把分治模板练熟才是正事。3.2 逆序对计数逆序对定义很简单i j 时若 a[i] a[j]这俩元素构成一个逆序对。暴力算法两两比较O(n²)数据量一上万就卡死。归并排序版的解法时间复杂度 O(n log n)原理非常巧妙。核心思想藏在合并阶段。假设当前需要合并左数组 [left, mid] 和右数组 [mid1, right]两边各自已经有序。当右数组的指针 j 指向的元素比左数组指针 i 指向的元素小时说明 a[i..mid] 里所有元素都大于 a[j]因为左数组是有序的a[i] 已经是左边区间里最小的那个所以 a[j] 和左数组剩余元素一一构成逆序对逆序对数量直接累加mid - i 1。long long mergeCount(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; int j mid 1; int k left; long long invCount 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { // arr[j] 与 a[i..mid] 所有元素都构成逆序对 invCount (mid - i 1); temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int idx left; idx right; idx) { arr[idx] temp[idx]; } return invCount; } long long mergeSortCount(vectorint arr, int left, int right, vectorint temp) { if (left right) { return 0; } int mid left ((right - left) 1); long long count 0; count mergeSortCount(arr, left, mid, temp); count mergeSortCount(arr, mid 1, right, temp); count mergeCount(arr, left, mid, right, temp); return count; }这里有一个特别容易踩的坑逆序对数量要开long long不能开int。一个长度为 100000 的数组如果完全逆序排列逆序对数量是 n(n-1)/2大约 5 × 10^9早就超出 int 的最大值 2.1 × 10^9 了。我之前因为偷懒用 int 交题WA 了一次才反应过来白白浪费十几分钟调试时间。3.3 小和问题小和问题和逆序对是同一套模板的两个变体。定义是数组中每个元素左边所有比它小的元素值之和累加所有元素就是小和。举个例子数组 [1, 3, 5, 2, 4]3 左边比它小的有 1贡献 15 左边比它小的有 1 和 3贡献 42 左边比它小的有 1贡献 14 左边比它小的有 1、3、2贡献 6总和是 12。暴力解是 O(n²)。归并解法的视角是反过来的与其统计每个元素左边有哪些更小值不如统计每个值作为“更小值”时被多少个右侧元素借用。合并时如果左数组当前元素 a[i] 小于等于右数组当前元素 a[j]说明 a[i] 比右数组从 j 到 right 的所有元素都小贡献就是a[i] * (right - j 1)。long long mergeSmallSum(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; int j mid 1; int k left; long long sum 0; while (i mid j right) { if (arr[i] arr[j]) { // arr[i] 小于右数组剩余元素累加贡献 sum (long long)arr[i] * (right - j 1); 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 idx left; idx right; idx) { arr[idx] temp[idx]; } return sum; }乘法运算这里同样要注意强制转long long避免两个 int 相乘溢出。这类归并统计问题只要吃透了逆序对那套“利用有序性批量计算”的思路基本可以举一反三。4. 归并的进阶场景不止于排序4.1 多路归并与外部排序归并思想在最基础的排序之外还有两个经典延伸场景多路归并和外部排序。先看多路归并。当你有 k 个已经有序的序列想合并成一个有序序列两两归并需要做 k-1 次归并。每次归并比较两个序列的头部元素复杂度可以接受但当序列数量很多时每轮寻找 k 个头部中的最小值需要 k-1 次比较整体效率会下降。工程上的做法是用一个大小为 k 的堆来维护 k 个序列的当前头部元素每次弹出最小值所在序列的头部然后从该序列补充下一个元素进堆。这样每次取最小值的代价从 O(k) 降到 O(log k)。更进一步的数据结构是败者树专门为多路归并设计在磁盘外部排序的场景里已经用了很多年。外部排序处理的是“内存装不下”的数据。假设内存只能放下 100MB但待排序文件有 10GB。思路是把大文件切成若干小块每块在内存内排好序写出成临时文件最后用多路归并把这些有序临时文件边读边合合并结果直接写到最终输出文件。归并排序在这里不只是算法题了它直接决定了数据库排序、日志排序这些基础功能的性能。我在实际项目里做过 GB 级日志文件的排序当时就是用了这个套路把内排序和外归并拆开处理稳得很。4.2 四边形不等式优化DP分治解法与二分解法归并能在排序过程中顺带统计信息已经属于进阶内容但分治思想还能再往前走一步优化动态规划。热搜里那个“四边形不等式优化 dp 分治解法 二分解法”是最容易让初学者懵圈的一类题。先交代背景。有些 DP 的状态转移形如 dp[i] min(dp[j] cost(j, i))暴力枚举所有 j 是 O(n²)。如果 cost 函数满足四边形不等式那么 DP 的最优决策点会随 i 单调递增也就是“决策单调性”。这个性质一起就能用分治在 O(n log n) 内求解。分治解法的核心是递归求解某个区间 [l, r] 的 dp 值时同时传入一个可能的决策点搜索区间 [optL, optR]每次枚举决策点时只在这个区间里找。算出中点 mid 的最优决策点 optMid 后递归求解左半区间时搜索区间收缩为 [optL, optMid]递归求解右半区间时搜索区间收缩为 [optMid, optR]。因为决策单调性保证了区间的收缩不会遗漏最优解总的枚举量被压缩到 O(n log n)。二分解法的思路是另一条路。既然决策点随 i 单调就可以逐个确定每个决策点“接管”的状态区间。常见实现是维护一个单调栈或双端队列每个队列元素保存“决策点 它作为最优决策的状态范围”新决策点加入时用二分找到它接管范围的边界。整体复杂度同样是 O(n log n)但编码细节和分治解法差异很大。我个人的体会是如果比赛或面试中遇到这类题优先考虑分治解法。原因很简单分治解法的代码模板和归并排序的递归结构相似思维负担小边界条件也更直观。二分栈的写法对边界非常敏感我自己写过几次每逢“开区间闭区间”“最优值相等时取哪个决策点”这些细节都会卡壳。你需要根据自己对哪种模板更熟悉来做选择。5. 踩坑实录分治代码的边界地狱5.1 递归边界你写对了吗分治递归最常见的错误就是边界处理。mergeSort里我用的边界是if (left right) return;这个写法做了两件事区间里有一个元素时返回区间为空时也返回。有的写法写if (left right)当调用方不小心传入空区间就会死循环或越界。建议一律写养成习惯。合并循环里的边界同样要小心。while (i mid j right)的两端边界都取等号因为两个子数组的元素都要被扫描到不能漏掉最后一个。拷贝回原数组时循环也是for (int idx left; idx right; idx)从 left 到 right不是从 0 开始也不是到 n-1 结束。5.2 mid 计算的防溢出写法mid left ((right - left) 1)这个写法我是强烈推荐的。老写法(left right) / 2在 left 和 right 都是 2^31 量级时可能溢出成负数结果完全错误。虽然普通刷题数据一般不会触发但工程代码里数组索引完全可能很大一次溢出就是隐蔽的 bug调试成本极高。新写法把减法优先算了永远不会溢出。还有一个小细节右移一位需要加括号因为运算符优先级里右移低于加减法。写成left (right - left) 1会变成(left right - left) 1实际等于right 1直接整段逻辑错乱。5.3 临时数组的复用与性能我见过很多初学者喜欢在 merge 函数内部写vectorint temp(right - left 1);逻辑没错但性能很差。每次合并都触发一次内存分配递归的每一层都会做很多次分配总分配次数是 O(n) 级别而内存分配本身是个昂贵操作。正确的做法是在mergeSort外层初始化一整个temp长度等于原数组长度然后递归过程中所有区间合并共用这块空间。因为合并操作是串行的同一个位置不会同时被两个合并使用安全得很。实测对 100 万元素的数组排序复用临时数组的版本比每次新建的版本快一倍以上这个优化是白赚的。5.4 相等元素顺序与稳定性归并合并时if (arr[i] arr[j])决定了稳定性。写成会变成不稳定排序虽然对纯数值排序结果没影响但如果你排序的是一个对象数组按某个字段排序稳定性和不稳定性的结果可能完全不同。举个例子先按时间排序再按优先级排序稳定排序能让相同优先级的元素保留原时间顺序不稳定排序则可能打乱。我在实际开发中确实遇到过一次这个需求。按订单创建时间排好序后需要再按用户等级分组排序同时保留组内的时间顺序。如果手写的归并排序用的是分组后时间顺序就乱了排查半天才发现是稳定性写错了。5.5 数据溢出的隐蔽炸弹归并的统计类问题里溢出的坑集中出现在两个地方逆序对数量和小和累加值。逆序对数量最大是 n(n-1)/2n10^5 时就达到约 5 × 10^9必须用long long。小和问题的累加值更夸张如果一个元素值是 10^9它在最坏情况下可能被累加 n 次总和的量级是 10^14连 int 的一个零头都装不下。不仅变量类型要注意乘法的中间结果也要转类型。arr[i] * (right - j 1)如果两个操作数都是 int乘法结果直接溢出赋值给 long long 也救不回来。正确写法是(long long)arr[i] * (right - j 1)先把一边转成 long long整个表达式自动提升为 long long 运算。我在实际解题中多次因为这些问题返工。分治本身不难难的是各种边界和类型细节。写完代码后一定自己构造几组数据测一下空数组、单元素、全部相等、完全逆序、完全有序。这些边界案例跑一遍比你在编译器里反复看代码管用得多。最后再分享一个小技巧调试分治代码时最好加一个打印函数把每层递归处理的区间 [left, mid, right] 和合并后的数组打印出来。这样你能直观看到递归是否按预期拆解合并是否真的有序。我过去调试归并二进制转储数据时靠这个手段十分钟就定位到了问题省去了两小时的怀疑人生。