归并排序的核心是分治三步：split切分、merge合并、combine写回；merge需用临时数组、半开区间、正确边界控制，且应复用辅助空间而非重复分配。
归并排序的核心逻辑是分治，不是递归本身
归并排序的正确理解起点不是“写个递归函数”，而是明确三步：split（切分到单元素）、merge（合并两个有序段）、combine（把合并结果写回原数组）。递归只是实现 split 的自然手段，但容易让人忽略 merge 的边界控制——这才是实际编码出错最多的地方。
- 切分时用
[left, right)半开区间比[left, right]更少出错，避免mid = (left + right) / 2溢出可改用mid = left + (right - left) / 2 -
merge必须用临时数组暂存结果，不能边合并边写回原数组，否则会覆盖未读取的数据 - 合并循环的终止条件不是“两个子数组都空”，而是“至少一个已耗尽”，剩余部分直接拷贝
标准实现中 merge 函数的四个关键参数
很多初学者把 merge 写成只接受两个独立数组的函数，这在归并排序里反而增加复杂度。实际应传入原数组指针 + 三段下标：arr、left、mid、right（mid 是左半段末尾+1，即右半段起始位置）。
-
left到mid-1是左有序段 -
mid到right-1是右有序段 - 合并结果要填回
arr[left]到arr[right-1] - 临时数组大小必须是
right - left，而非固定长度或arr.size()
避免内存重复分配的常见优化
每次递归都 new 临时数组会导致大量堆分配，尤其对大数组性能敏感。更合理的方式是在顶层调用时一次性分配好辅助空间，全程复用。
void mergeSort(vector& arr) { if (arr.size() <= 1) return; vector temp(arr.size()); // 一次分配 mergeSortHelper(arr, temp, 0, arr.size()); } void mergeSortHelper(vector
& arr, vector & temp, int left, int right) { if (right - left <= 1) return; int mid = left + (right - left) / 2; mergeSortHelper(arr, temp, left, mid); mergeSortHelper(arr, temp, mid, right); merge(arr, temp, left, mid, right); }
-
temp作为引用传入，避免拷贝 -
merge内部只操作temp的对应区间，再批量拷贝回arr - 若用原始指针（如
int*），需额外传入temp起始地址，逻辑不变
迭代版归并排序为什么更难写对
递归版天然体现分治结构，而迭代版靠自底向上合并：先两两合并长度为 1 的段，再合并长度为 2 的段……容易错在 right 边界越界和最后一段长度不足时的处理。
立即学习“C++免费学习笔记（深入）”；
- 外层循环步长
len从 1 开始，每次翻倍：for (int len = 1; len - 内层循环起点
i每次加2 * len，但right = min(i + 2 * len - 1, n - 1)必须取最小值 - 右半段可能不存在（
i + len >= n），此时跳过合并 - 即使知道原理，手写迭代版仍建议先跑通递归版，再对照改写，否则调试成本极高
归并排序真正卡住人的地方，从来不是“怎么分”，而是“合并时下标算错一格，整段结果就乱序”，尤其是 mid 和 right 的开闭关系、临时数组拷贝的起始偏移。写完务必用 {5, 2, 4, 7, 1} 这类小样例单步验证 merge 调用前后的子数组内容。
