c++oding="utf-8" ?>
std::stable_sort本质是自底向上的归并排序，通过合并时优先取左半段相等元素保证稳定性，主流实现（libstdc++、libc++）以此满足稳定性和O(N log N)平均复杂度要求。
std::stable_sort 本质是归并排序，不是插入排序
它不保证用某一种固定算法实现，但标准要求必须稳定且平均时间复杂度为 O(N log N)。主流实现（libstdc++、libc++）都基于**自底向上的归并排序**，部分场景会切到插入排序优化小数组——但这只是内部优化，不影响稳定性。
关键点在于：归并过程严格保持相等元素的原始相对顺序。比如左半段有个 a[i] 和右半段有个 a[j] 满足 !comp(a[j], a[i]) && !comp(a[i], a[j])（即相等），归并时优先取左半段的元素。
为什么 std::sort 不稳定而 stable_sort 稳定
根本区别不在“是否比较相等”，而在**算法设计对相等元素的处理逻辑**：
-
std::sort通常用 introsort（快排 + 堆排 + 插入排序混合），快排分区时可能把相同值的元素跨区间交换，破坏原始顺序 -
std::stable_sort的归并操作天然保序：左右子序列各自已有序，合并时只要在相等情况下始终先取左侧，就能守住稳定性 - 即使你传入的
comp把两个不同对象判为“等价”，std::stable_sort仍按它们在原容器中的位置决定先后
使用时要注意的三个实际细节
稳定性不是免费的——它带来空间和缓存行为上的代价：
- 必须有额外空间：libstdc++ 默认申请
std::max(1, N) * sizeof(T)的临时缓冲区；若内存不足，会退化为O(N log²N)的分治归并（不分配大块内存，但递归更深） - 自定义比较器不能修改元素状态，否则可能破坏稳定性前提（比如在
comp里偷偷改了某个成员变量） - 对
std::list或std::forward_list，std::stable_sort有特化版本，只用常数额外空间（靠指针重连，不移动元素值）
示例：对含重复 key 的结构体排序，验证稳定性
struct Item { int key; int id; };
std::vector<item> v = {{2,1}, {1,2}, {2,3}, {1,4}};
std::stable_sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
return a.key <h3>别指望它解决所有“顺序保留”问题</h3>
<p>稳定性只承诺：**输入中先出现的相等元素，在输出中依然在前**。但它不保证：</p>
<ul>
<li>多线程环境下迭代器或引用是否失效（排序过程会移动元素，<code>std::vector</code> 可能 realloc）</li>
<li>自定义类型若没有正确实现移动/拷贝语义，可能导致未定义行为（尤其是移动构造抛异常时）</li>
<li>与 <code>std::partial_sort</code> 或 <code>std::nth_element</code> 混用时，稳定性不成立——那些函数根本没承诺稳定</li>
</ul>
<p>真正容易被忽略的是：当你用 <code>std::stable_sort</code> 处理大型 <code>std::vector<:string></:string></code> 时，临时缓冲区分配失败不会抛 <code>std::bad_alloc</code>，而是默默切换成低效路径，性能可能陡降一个数量级，却无任何警告。</p></item>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
