归并排序核心是分治且非原地排序，需额外空间合并子数组；递归版有栈溢出风险，应设终止条件并小数组转插入排序；迭代版更安全但边界易错；泛化需适配迭代器与移动语义。
归并排序的核心逻辑是分治，不是原地排序
归并排序在 C++ 中必须额外分配空间来合并两个有序子数组，这点和 std::sort（通常是 introsort）有本质区别。如果你试图“原地归并”，会陷入高复杂度的旋转操作，实际项目中几乎没人这么做。标准实现依赖一个临时缓冲区，大小至少为待排序区间的长度。
递归写法要注意栈溢出风险
对百万级元素递归调用 mergeSort 可能导致栈溢出，尤其在默认栈大小的 Windows 或嵌入式环境。常见错误是没设递归终止条件或忽略小数组优化：
- 必须检查
left >= right作为递归基 - 建议在子数组长度 ≤ 16 时切换到插入排序（
std::sort内部也这么干） - 避免每次递归都 new/delete 临时数组；应一次性分配好，传引用复用
void merge(std::vector& arr, std::vector & temp, int left, int mid, int right) { int i = left, j = mid + 1, k = left; 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 (i = left; i <= right; ++i) arr[i] = temp[i]; }
迭代版更安全，但容易写错区间边界
迭代归并避免递归开销，适合大数组或栈受限场景，但 for 循环里控制子数组长度（width）、起始点（left）、中点（mid）和终点（right）极易越界。典型错误包括：
-
mid = min(left + width - 1, n - 1)忘记取min，导致mid >= n -
right = min(left + 2 * width - 1, n - 1)没加保护，合并时访问非法内存 - 临时数组未覆盖整个
[left, right]区间，造成部分数据未更新
void mergeSortIterative(std::vector& arr) { int n = arr.size(); std::vector temp(n); for (int width = 1; width < n; width *= 2) { for (int left = 0; left < n - width; left += 2 * width) { int mid = std::min(left + width - 1, n - 1); int right = std::min(left + 2 * width - 1, n - 1); merge(arr, temp, left, mid, right); } } }
STL 容器适配要考虑迭代器和移动语义
若想把归并排序泛化到任意容器（如 std::list、std::deque），不能直接索引，得用迭代器 + std::distance 和 std::advance。但注意：std::list 的随机访问是 O(n)，强行套用数组版归并会退化成 O(n² log n)。更合理的方式是利用 std::list::merge —— 它本身就是稳定、O(n) 的归并操作。
立即学习“C++免费学习笔记（深入）”；
对支持移动语义的类型（如 std::string、自定义类），记得在拷贝到 temp 时用 std::move，否则可能触发深拷贝：
temp[k++] = std::move(arr[i++]);
归并排序真正难的不是写出来，而是根据数据规模、内存限制、容器类型和元素开销，选对实现路径——递归/迭代、临时空间复用策略、是否启用移动、以及何时交给 std::sort 更省事。
