归并排序采用分治策略且非原地排序，需额外空间合并子段；推荐左闭右开区间[left, right)，注意临时数组大小、边界检查及栈溢出风险。
归并排序的核心逻辑是分治，不是原地排序
归并排序在 C++ 中必须额外分配空间，不能像 std::sort 那样直接对原数组“就地”重排。这是因为归并过程需要两个已排序子段的临时合并缓冲区，强行复用原数组容易覆盖未读取数据。常见错误是试图用单个临时数组反复覆盖，结果出现越界或数据错乱。
典型使用场景：需要稳定排序、数据量中等（几万到百万级）、内存充足；不适合嵌入式或内存极度受限环境。
- 递归分治时，
left和right边界要统一用闭区间或左闭右开，推荐用[left, right)避免边界计算出错 - 临时数组大小必须至少为当前待合并段长度，每次
merge前重新new或复用预分配缓冲区 - 递归深度约
log₂(n)，对超大数组（如 >10⁷）可能栈溢出，需改写为迭代版本
如何写一个安全可用的 merge 函数
merge 是归并排序的骨架，它不关心怎么分，只负责把两个相邻有序段合并成一个有序段。关键在于索引控制和边界检查——漏掉一个 ++ 或写反 就会丢数据或死循环。
示例片段（假设输入为 int 数组，使用左闭右开区间）：
void merge(int arr[], int temp[], int left, int mid, int right) {
int i = left, j = mid, k = left;
while (i
-
temp必须与原数组同类型，且长度 ≥right - left - 合并后必须拷回原数组，否则上层递归看到的仍是未排序数据
- 若用
std::vector代替裸数组，注意vector的data()返回指针，可直接传给上述函数
递归实现里最容易漏掉的终止条件
归并排序递归函数的退出点不是 size == 1，而是 left >= right - 1（对应左闭右开区间下长度 ≤ 1）。写成 if (left == right) 会导致单元素段不触发合并，而 if (left >= right) 又会让空区间误入递归。
标准写法：
void mergeSort(int arr[], int temp[], int left, int right) {
if (right - left
- 调用入口应为
mergeSort(arr, temp, 0, n)，不是n-1 -
mid计算用left + (right - left) / 2防止left + right溢出（尤其在int大数组下） - 如果用
std::vector，传&vec[0]要确保 vector 非空，否则&vec[0]未定义
用 std::vector 实现时要注意内存和迭代器失效
用 std::vector 包装归并排序更安全，但别以为“自动管理内存”就万事大吉。常见坑是临时 vector 在每次 merge 里重建，导致频繁堆分配拖慢性能；或者误用 push_back 替代下标赋值，破坏时间复杂度。
- 最优做法：在顶层一次性分配
temp为vector<int>(n)</int>，全程复用 - 不要在
merge内部调用temp.clear()或temp.resize()，这会引发重新分配 - 避免用
vector::begin()+ 算术运算传参，直接传&vec[0]或用data()更清晰 - 若需泛型支持，模板参数必须约束为可比较、可赋值类型，否则编译报错信息会指向
merge内部而非调用处
真正麻烦的从来不是算法逻辑，而是临时空间生命周期管理、边界数值精度、以及递归调用栈和堆分配的隐式成本。写完跑通只是第一步，压测时才发现 temp 分配位置不对，或 mid 计算在 size_t 下溢出，这类问题不会报错，只会让排序结果偶尔错乱。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
