# 认识“分治”思想
⚡ 30 秒速记
- 分治三步：拆成同类小问题 → 分别解决 → 合并结果
- 递归要有基线（比如长度
≤ 1直接返回），每次拆分规模必须严格变小 - 合并是关键，只拆不合等于没做
- 归并排序：拆分简单、合并费力；快速排序：拆分（分区）费力、合并不用做
- 递归太深可以改成自底向上迭代，分治思想不变
分治就是把大问题拆成几个同样结构的小问题，各自解决，再把结果合起来。 好比一个班的试卷让一个人改太慢，拆给四个组各改一摞，最后汇总分数。排序里的两个经典例子：归并排序拆分很简单，从中间切开就行，力气花在合并上；快速排序正好反过来，力气花在分区上，分完左右各自排好就天然有序，不用合并。写递归时我会先确认两件事：基线是什么，每次拆分规模是不是一定变小。
本节我们要学习的两个排序算法都是对“分治”思想的应用。 “分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。
利用分治思想解决问题，我们一般分三步走：
- 分解子问题
- 求解每个子问题
- 合并子问题的解，得出大问题的解
下面我们一起来看看分治思想是如何帮助我们提升排序算法效率的。
💬 面试官追问
-
数组切两半，各自排好后直接拼起来，算分治吗？
不算完整的分治，少了合并。
[3, 4]和[1, 2]各自有序，直接拼是[3, 4, 1, 2]，还是乱的，得用双指针合并。 -
写一个分治排序的递归函数，入参、返回值和终止条件怎么定？
入参是数组或
[lo, hi)区间，返回有序结果，长度≤ 1直接返回。区间开闭全程统一用左闭右开，切分点mid = (lo + hi) >> 1，不会漏也不会重叠。 -
数据太大，递归太深栈溢出，要放弃分治吗？
不用，换实现方式就行。归并可以写成自底向上：先两两合并长度
1的段，再合并长度2的，以此类推。其实归并递归深度只有log n，100万条才20层，真栈溢出多半是切分写错导致不收敛。 -
线上排序结果偶尔少元素，叶子节点都没问题，先查哪？
查合并。最常见的是一侧耗尽后忘了把另一侧剩余部分接上。加个断言：合并结果长度等于左右长度之和。
-
快排和归并都是分治，区别在哪？
归并先拆后合，排序发生在合并阶段，稳定、时间稳定
O(n log n)，但要O(n)辅助空间。快排先分区再递归，原地排，平均O(n log n)，最坏O(n²)，不稳定。
# 归并排序
⚡ 30 秒速记
- 一直对半切到单个元素，再两两用双指针合并成有序段
- 递归只负责拆，真正的排序发生在合并
- 每层合并处理
n个元素，共log n层 → 稳定O(n log n)，不分好坏情况 - 数组版要
O(n)辅助空间；相等时先取左边才稳定（<=而不是<） - 适合链表排序、外部排序、要求稳定的场景
归并排序就是先把数组一直对半切到只剩一个元素，再两两合并，合并时用双指针保证每次合出来都是有序的。 单个元素天然有序，所以整件事就变成了反复合并两个有序数组，这一步是线性的。一共 log n 层，每层合并所有 n 个元素，所以不管输入什么样都是 O(n log n)，这是它比快排稳的地方。代价是数组版要 O(n) 的额外空间。合并时两边相等要先取左边，写成 <=，不然就不稳定了。
