归并排序不能完全避免额外空间；标准实现需O(n)辅助空间完成O(n)合并，迭代法可消除O(log n)递归栈空间但无法省略merge缓冲区，原地merge会导致O(n²)时间复杂度。
归并排序能不用额外空间吗？
不能完全避免，但可以大幅减少——标准归并排序的 merge 过程必须有 O(n) 辅助空间，否则无法在 O(n) 时间内完成合并。所谓“不使用额外递归空间”，实际是指消除递归调用栈的 O(log n) 深度开销，改用迭代（bottom-up）实现；而 merge 所需的临时缓冲区仍不可省略。强行原地 merge（如通过旋转或交换）会导致时间退化到 O(n²)，得不偿失。
如何用迭代方式替代递归，消除栈空间？
把递归的“分治”逻辑翻过来：从子数组长度为 1 开始，逐轮合并相邻有序段，子数组长度翻倍（1 → 2 → 4 → …），直到覆盖整个数组。每轮用循环控制区间，不依赖函数调用栈。
关键点：
- 用
subsize表示当前待合并的子数组长度，初始为 1 - 外层循环条件是
subsize ，每次 <code>subsize *= 2 - 内层循环遍历所有起始位置
left，满足left + 2 * subsize - 1 的才完整包含两个子数组；剩余不足部分单独处理（<code>mid = min(left + subsize - 1, n - 1)，right = min(left + 2 * subsize - 1, n - 1)） - 每次调用
merge(arr, left, mid, right)，该函数仍需 O(subsize) 临时空间，但总空间复用，峰值仍是 O(n)
merge 函数要不要自己写？能不能复用 std::inplace_merge？
不能用 std::inplace_merge 实现“真正原地”，它虽不暴露额外分配，但标准要求其复杂度为 O(n)，实际实现（如 libstdc++）仍会申请临时缓冲区 —— 它只是把内存管理封装了，并未减少空间开销。你自己写 merge 更可控，也便于调试。
立即学习“C++免费学习笔记（深入）”；
一个轻量可靠的 merge 示例：
void merge(std::vector<int>& arr, int left, int mid, int right) {
std::vector<int> 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++];
std::copy(temp.begin(), temp.end(), arr.begin() + left);
}
注意：temp 在每次 merge 调用时重建，但可优化为在整个迭代排序前预分配一次固定大小的 std::vector<int> temp(n) 并复用，避免频繁构造/析构。
性能和边界容易出错的地方
迭代归并比递归版本更易写错索引，尤其在处理末尾不完整段时：
-
mid必须取min(left + subsize - 1, n - 1)，否则越界访问 -
right是min(left + 2 * subsize - 1, n - 1)，不是n - 1固定值 - 当
left + subsize >= n时，第二个子数组不存在，无需合并，直接跳过 - 编译器对
std::vector的operator[]不做边界检查，越界不会报错但行为未定义 - 若数据类型重载了
<或涉及移动语义，确保temp中存储的是可拷贝/可移动对象
最常被忽略的是：即使消除了递归栈，O(n) 临时空间仍是硬性需求。试图用 swap+rotate 模拟原地合并，会在随机数据上显著拖慢运行速度，别为“原地”二字牺牲实用性。
