归并排序的核心是分治与合并，需用临时vector暂存结果，不可原地合并；采用左闭右开区间[l,r)，递归切分后线性合并，模板实现应支持任意可比较类型并处理边界安全。
归并排序的核心逻辑是分治 + 合并，不是原地排序
归并排序必须额外分配空间来暂存合并结果，std::vector 是最稳妥的选择。用 std::array 或裸数组容易越界或长度写死；试图在原数组上“就地合并”会破坏分治前提，实际不可行。
关键点在于：递归切分到单元素后，再逐层向上合并两个已序子段。合并过程本身是线性扫描，但必须用临时容器承接，否则覆盖未读取数据。
- 切分边界用左闭右开区间（
[l, r)）更安全，避免r-1手动计算出错 - 每次合并前分配大小为
r - l的临时std::vector，避免反复push_back引发多次扩容 - 合并完成后一次性拷贝回原数组对应位置，不要边合并边写入
如何写一个可复用的 merge_sort 函数
直接封装成模板函数，支持任意可比较类型。重点处理好迭代器或索引接口——推荐用索引，避免迭代器失效和随机访问性能问题。
示例实现：
template <typename t>
void merge_sort(std::vector<t>& arr, int l = 0, int r = -1) {
if (r == -1) r = arr.size();
if (r - l int m = l + (r - l) / 2;
merge_sort(arr, l, m);
merge_sort(arr, m, r);
std::vector<t> tmp(r - l);
int i = l, j = m, k = 0;
while (i <p>}</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></t></t></typename>
注意：r 默认值用 -1 而非 arr.size()，是因为模板参数不能依赖运行时值；调用时传 merge_sort(vec) 即可自动适配全范围。
常见错误：合并时下标越界或漏拷贝
典型错误现象是排序后部分元素消失、重复或乱序，多因合并循环条件或边界处理不当。
- 误写
while (i 为 <code>while (i → 越界访问 - 漏掉剩余段拷贝（即两个
while），导致右半段较大元素未写入tmp - 拷贝回原数组时用
std::copy(tmp.begin(), tmp.end(), arr.begin() + l)，而非arr.begin() + i等动态偏移 - 临时
tmp大小写成m - l或r - m，而非r - l→ 缓冲区不足
性能与稳定性：为什么它适合大数据量但慎用于小数组
时间复杂度稳定 O(n log n)，不随输入顺序变化，这是它比快排可靠的地方；但常数因子大，且每层都要分配/释放临时内存。
- 对
n 的子数组，建议切换到插入排序（<code>std::sort内部就做这个优化） - 避免频繁构造
std::vector：可将临时缓冲区作为参数传入，复用同一块内存 - 若需稳定排序且数据在磁盘或链表中，归并仍是首选——但标准库
std::list::sort就是归并实现，别自己重写
真正麻烦的是边界条件和内存管理，而不是逻辑本身。写一次能跑通不难，但要让它在各种 size = 0, 1, 2, INT_MAX-1 下都不崩，得盯紧每处 l、m、r 的关系。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
