分治法需手动拆解、递归处理与合并，关键在拆分时机、合并方式及边界设定；mergesort稳定o(n log n)但耗空间，quicksort平均快但最坏o(n²)，需随机化pivot；merge易漏处理单边耗尽、空区间及mid溢出；最大子数组和须返回结构体以支持跨中点合并。
分治法不是“用一个函数调用就能启用”的机制，而是必须手动拆解问题、递归处理、再合并结果的编程模式。直接套模板会出错，关键在判断何时拆、怎么合、边界怎么设。
什么时候该写 mergeSort 而不是 quickSort
两者都是分治，但适用前提不同：
-
mergeSort保证O(n log n)时间，适合对时间稳定性有要求的场景（比如实时日志排序、嵌入式系统）；它的合并步骤必须额外分配空间，内存紧张时要注意vector或临时数组的生命周期 -
quickSort平均快但最坏退化到O(n²)，如果输入可能有序（如传感器连续采样值），不加随机化基准就容易卡死；partition函数里swap(arr[rnd], arr[right])这一步不能省 - 若数据已部分有序，
mergeSort的实际耗时接近O(n)，而quickSort可能更慢——这不是理论缺陷，是 pivot 选得差导致的递归树倾斜
merge 函数里最容易漏掉的三件事
合并两个有序段时，常见错误不是逻辑错，而是边界和资源管理疏忽：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 没处理某一边提前耗尽的情况：必须补全剩余元素，不能只靠
while(i 就结束 - 用
vector临时存储时，没 resize 或没清空，导致旧数据残留；建议每次新建局部vector<int> temp</int>，而不是复用外部变量 - 复制回原数组时下标越界：例如
for(int k = left; k 写成 <code>k ，漏掉最后一个元素
递归终止条件写成 if (left >= right) 还是 if (left == right)
取决于你传入的区间定义方式：
- 若用闭区间
[left, right]（推荐），终止条件必须是if (left >= right)——因为当left == right时只剩一个元素，无需再分；而left > right可能出现在空区间（如mid+1 > right），也应直接返回 - 若误写成
if (left == right)，当left > right时会继续递归，触发栈溢出或访问非法内存 - 计算
mid时用left + (right - left) / 2，避免(left + right)整数溢出（尤其在指针或大索引场景）
分治解最大子数组和时，为什么不能只返回数值？
因为合并阶段需要知道左半段的“后缀最大和”和右半段的“前缀最大和”，仅存一个 int 值无法支撑跨中点的组合：
- 必须定义结构体或 tuple，至少携带三个信息：
maxSum、leftSum（从左端开始的最大连续和）、rightSum（到右端结束的最大连续和） - 跨中点的最大和 =
left.rightSum + right.leftSum，不是简单相加左右最大值 - 如果只返回标量，合并逻辑会退化为暴力扫描，失去分治意义
分治真正的复杂点不在递归本身，而在“合”的设计——它必须可逆、无损、且能覆盖所有子问题组合路径。多数 bug 出现在合并逻辑遗漏分支，而非分解过程。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
