c++oding="utf-8" ?>
归并排序不能完全避免额外空间；标准实现需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 更可控，也便于调试。
一个轻量可靠的 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 <p>注意：<code>temp</code> 在每次 <code>merge</code> 调用时重建，但可优化为在整个迭代排序前预分配一次固定大小的 <code>std::vector<int> temp(n)</int></code> 并复用，避免频繁构造/析构。</p>
<h3>性能和边界容易出错的地方</h3>
<p>迭代归并比递归版本更易写错索引，尤其在处理末尾不完整段时：</p>
<ul>
<li>
<code>mid</code> 必须取 <code>min(left + subsize - 1, n - 1)</code>，否则越界访问</li>
<li>
<code>right</code> 是 <code>min(left + 2 * subsize - 1, n - 1)</code>，不是 <code>n - 1</code> 固定值</li>
<li>当 <code>left + subsize >= n</code> 时，第二个子数组不存在，无需合并，直接跳过</li>
<li>编译器对 <code>std::vector</code> 的 <code>operator[]</code> 不做边界检查，越界不会报错但行为未定义</li>
<li>若数据类型重载了 <code> 或涉及移动语义，确保 <code>temp</code> 中存储的是可拷贝/可移动对象</code>
</li>
</ul>
<p>最常被忽略的是：即使消除了递归栈，O(n) 临时空间仍是硬性需求。试图用 swap+rotate 模拟原地合并，会在随机数据上显著拖慢运行速度，别为“原地”二字牺牲实用性。</p></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
