归并排序需统一使用左闭右闭区间，mid = left + (right - left) / 2，子区间为[left, mid]和[mid+1, right]；merge时先复制待合并段到临时数组，再双指针归并，最后必须拷回剩余元素。
归并排序在 C++ 里用递归实现并不难，但容易在边界处理、临时数组拷贝、索引越界上出错。核心是「分治 + 合并」，关键不在写对，而在写稳。
merge 函数怎么写才不越界
合并两个已排序子区间时，常见错误是 left、mid、right 的开闭区间理解混乱，导致访问 arr[mid+1] 越界或漏掉最后一个元素。
- 统一用左闭右闭区间：即子数组范围是
[left, right]，则中点为mid = left + (right - left) / 2，左右子区间分别是[left, mid]和[mid+1, right] -
merge函数接收arr、left、mid、right，先复制整个待合并段到临时数组（避免原地覆盖），再双指针归并回原数组 - 合并循环结束后，必须把左右两段剩余元素全部拷回——不能只靠
i 或j 中的一个判断
void merge(vector& arr, int left, int mid, int right) { vector temp(right - left + 1); int i = left, j = mid + 1, k = 0; 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 = 0; idx < temp.size(); ++idx) { arr[left + idx] = temp[idx]; } }
mergesort 递归调用的终止条件和参数传递
递归函数入口常写成 mergesort(arr, 0, arr.size()-1)，但终止条件若写成 if (left == right) 没问题；若用 if (left >= right) 更安全，能兼容空数组（size()==0）和单元素情况。
- 每次递归前必须检查
left ，否则mid计算可能无效，且会无限递归 - 递归调用顺序：先
mergesort(arr, left, mid)，再mergesort(arr, mid+1, right)，最后merge(...)；顺序反了会导致子数组未排序就合并 - 不要传
vector值拷贝——必须传引用vector，否则排序无效&
vector 作为容器时要注意内存和性能
每层 merge 都新建 temp 数组，频繁分配释放会影响性能。实际项目中可考虑预分配一个全局临时缓冲区（大小等于原数组），避免重复 new/delete。
立即学习“C++免费学习笔记（深入）”；
- 小数组（比如
size ）直接用插入排序更高效，可在递归到底层时切换：if (right - left + 1 - 如果输入是
int*和长度，记得把right设为n-1，别误用n当右边界 - STL 迭代器版本虽灵活，但初学建议先掌握基于下标索引的写法，避免
std::distance和迭代器失效干扰逻辑
最常被忽略的是：合并时临时数组的索引偏移计算——arr[left + idx] 这一步漏加 left，会导致只改了数组开头部分，后半段根本没更新。这个 bug 不报错，但结果全乱。
