归并排序的核心逻辑是分治且非原地排序，需用临时缓冲区合并子数组；常见错误包括未深拷贝、内存泄漏、频繁分配导致空间退化；merge函数易错在边界越界与拷贝方向。
归并排序的核心逻辑是分治，不是原地排序
归并排序必须额外分配空间来合并两个已排序子数组，所以手写时第一步就得想清楚：临时缓冲区怎么管理。常见错误是直接在原数组上反复拷贝，导致时间翻倍或越界——比如用 vector<int>&</int> 传参却忘了深拷贝，或者手动管理 new int[n] 后没 delete[]，造成内存泄漏。
推荐做法是每次递归都传入一个复用的临时缓冲区（temp），大小与待排序段一致，避免频繁 new/delete；或者用 vector<int></int> 自动管理，但注意别在每层递归里构造新 vector，否则 O(n log n) 额外空间会退化成 O(n²) 分配开销。
merge 函数最容易写错边界和拷贝方向
合并两个升序子数组 [left, mid] 和 [mid+1, right] 时，典型错误包括：下标越界（比如 i 写成 <code>i ）、漏拷贝剩余元素、把 <code>temp 拷回原数组时范围不对。
- 左右指针初始值必须是
int i = left, j = mid + 1，不是0或1 - 合并循环条件应为
i ，不能漏等号 - 合并完后必须分别处理左/右子数组剩余部分：
while (i 和 <code>while (j - 最后拷贝回原数组的范围是
for (int k = left; k ，不是从 <code>0开始
示例关键片段：
void merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
for (int i = left; i <h3>递归终止条件和区间划分要严格对应</h3>
<p>归并排序的递归基是子数组长度为 1，即 <code>left >= right</code>。如果写成 <code>left == right</code>，当输入为空数组（<code>left > right</code>）时会无限递归；如果用闭区间 <code>[left, right]</code> 就必须用 <code>mid = left + (right - left) / 2</code>，而不是 <code>(left + right) / 2</code>（虽在 int 范围内通常安全，但有溢出风险）。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>区间划分必须保证左右两半覆盖完整且不重叠：</p>
<ul>
<li>左半：<code>[left, mid]</code>，右半：<code>[mid + 1, right]</code>
</li>
<li>调用时必须是 <code>mergeSort(arr, temp, left, mid)</code> 和 <code>mergeSort(arr, temp, mid + 1, right)</code>
</li>
<li>不能写成 <code>mid - 1</code> 或漏掉 <code>+1</code>，否则中间元素丢失或重复</li>
</ul>
<h3>C++ 中 vector 传参和迭代器版本的取舍</h3>
<p>用 <code>vector<int>&</int></code> 传引用最直接，但要注意调用方必须确保 <code>temp</code> 容量足够（至少等于 <code>arr.size()</code>）。如果想封装成通用函数，可用迭代器接口，但要注意：标准库没有提供原生 <code>merge</code> 的 inplace 版本，所以仍需外部缓存。</p>
<p>不建议初学时强行写模板迭代器版——容易在 <code>distance</code>、<code>advance</code>、随机访问判断上出错。先用索引版跑通逻辑，再考虑泛化。</p>
<p>真正容易被忽略的是：归并排序稳定性的保障全靠 <code> 判断（不是 <code>）。如果合并时写成 <code>if (temp[i] ，相等元素的相对顺序可能颠倒，稳定性就丢了。</code></code></code></p></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
