归并排序的核心逻辑是分治且非原地排序，需用临时缓冲区合并子数组；常见错误包括未深拷贝、内存泄漏、频繁分配导致空间退化；merge函数易错在边界越界与拷贝方向。
归并排序的核心逻辑是分治，不是原地排序
归并排序必须额外分配空间来合并两个已排序子数组，所以手写时第一步就得想清楚：临时缓冲区怎么管理。常见错误是直接在原数组上反复拷贝，导致时间翻倍或越界——比如用 vector<int>&</int> 传参却忘了深拷贝，或者手动管理 new int[n] 后没 delete[]，造成内存泄漏。
推荐做法是每次递归都传入一个复用的临时缓冲区（temp），大小与待排序段一致，避免频繁 new/delete；或者用 vector<int></int> 自动管理，但注意别在每层递归里构造新 vector，否则 O(n log n) 额外空间会退化成 O(n²) 分配开销。
merge 函数最容易写错边界和拷贝方向
合并两个升序子数组 [left, mid] 和 [mid+1, right] 时，典型错误包括：下标越界（比如 i 写成 <code>i ）、漏拷贝剩余元素、把 <code>temp 拷回原数组时范围不对。
- 左右指针初始值必须是
int i = left, j = mid + 1，不是0或1 - 合并循环条件应为
i ，不能漏等号 - 合并完后必须分别处理左/右子数组剩余部分：
while (i 和 <code>while (j - 最后拷贝回原数组的范围是
for (int k = left; k ，不是从 <code>0开始
示例关键片段：
立即学习“C++免费学习笔记（深入）”；
void merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
for (int i = left; i <= right; ++i) temp[i] = arr[i];
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) arr[k++] = temp[i++];
else arr[k++] = temp[j++];
}
while (i <= mid) arr[k++] = temp[i++];
while (j <= right) arr[k++] = temp[j++];
}递归终止条件和区间划分要严格对应
归并排序的递归基是子数组长度为 1，即 left >= right。如果写成 left == right，当输入为空数组（left > right）时会无限递归；如果用闭区间 [left, right] 就必须用 mid = left + (right - left) / 2，而不是 (left + right) / 2（虽在 int 范围内通常安全，但有溢出风险）。
区间划分必须保证左右两半覆盖完整且不重叠：
- 左半：
[left, mid]，右半：[mid + 1, right] - 调用时必须是
mergeSort(arr, temp, left, mid)和mergeSort(arr, temp, mid + 1, right) - 不能写成
mid - 1或漏掉+1，否则中间元素丢失或重复
C++ 中 vector 传参和迭代器版本的取舍
用 vector<int>&</int> 传引用最直接，但要注意调用方必须确保 temp 容量足够（至少等于 arr.size()）。如果想封装成通用函数，可用迭代器接口，但要注意：标准库没有提供原生 merge 的 inplace 版本，所以仍需外部缓存。
不建议初学时强行写模板迭代器版——容易在 distance、advance、随机访问判断上出错。先用索引版跑通逻辑，再考虑泛化。
真正容易被忽略的是：归并排序稳定性的保障全靠 判断（不是 <code>）。如果合并时写成 <code>if (temp[i] ，相等元素的相对顺序可能颠倒，稳定性就丢了。
