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仍按它们在原容器中的位置决定先后
使用时要注意的三个实际细节
稳定性不是免费的——它带来空间和缓存行为上的代价：
立即学习“C++免费学习笔记（深入）”；
- 必须有额外空间：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 < b.key;
});
// 结果一定是 [{1,2}, {1,4}, {2,1}, {2,3}] —— 同 key 内部 id 顺序不变
别指望它解决所有“顺序保留”问题
稳定性只承诺：**输入中先出现的相等元素，在输出中依然在前**。但它不保证：
- 多线程环境下迭代器或引用是否失效（排序过程会移动元素，
std::vector可能 realloc） - 自定义类型若没有正确实现移动/拷贝语义，可能导致未定义行为（尤其是移动构造抛异常时）
- 与
std::partial_sort或std::nth_element混用时，稳定性不成立——那些函数根本没承诺稳定
真正容易被忽略的是：当你用 std::stable_sort 处理大型 std::vector<:string></:string> 时，临时缓冲区分配失败不会抛 std::bad_alloc，而是默默切换成低效路径，性能可能陡降一个数量级，却无任何警告。
