stable_sort 不只是“稳定”，它还能并行——C++17 里被低估的排序利器

上周帮同事调一个老项目，数据量涨到百万级后，UI 列表突然开始“跳序”：同名用户反复拖拽后，顺序总在变。查了半天，发现他用的是 std::sort 对含时间戳的结构体排序，而比较函数只比了姓名字段——相等元素的相对位置被重排了。改用 stable_sort 后，问题当场消失。这让我想起：很多人知道它“稳定”，却很少人真去翻它的并行能力。

C++17 标准悄悄给 stable_sort 加了一把新钥匙：支持执行策略（Execution Policy）。不是所有编译器都默认开，但只要你用的是 GCC 9+、Clang 7+ 或 MSVC 2019 Update 3+，加上 -std=c++17 和对应优化开关，它就能真正并行跑起来。

关键不在“能不能”，而在“值不值得”。stable_sort 的底层实现通常是归并排序（MSVC 用的是自底向上归并，GCC/Clang 多用混合策略），天然适合分治并行。它不像 sort 那样依赖快速排序的原地交换——归并需要额外空间，但换来的是可预测的 O(n log n) 时间和稳定的顺序保证。这个“代价”，恰恰成了并行化的友好接口。

怎么启用？三行代码的事：

#include <algorithm>
#include <execution> // 注意：必须包含此头文件

std::vector<Record> data = /* ... */;
std::stable_sort(std::execution::par_unseq, data.begin(), data.end(), 
                 [](const auto& a, const auto& b) { return a.name < b.name; });

注意两个细节：

• par_unseq 是当前最激进的策略，允许编译器自动向量化 + 多线程，但要求比较函数无副作用、无外部状态依赖；
• stable_sort 的并行版本不支持自定义分配器（标准明确禁止），如果你用 std::pmr::vector，得先切回默认内存池再调用。

有人问：“我数据才几千条，开并行反而慢？”没错。并行有启动开销：线程创建、任务切分、临时缓冲区分配……实测表明，元素数量低于 5 万时，单线程 stable_sort 通常更快；超过 10 万，优势开始明显；到 100 万以上，并行提速常达 2.5–3.8 倍（取决于 CPU 核心数和内存带宽）。这不是玄学，是归并排序中“合并阶段”的天然并行粒度决定的。

更实用的提醒：别指望它自动解决所有稳定性问题。比如你按“部门→入职年份”两级排序，错误写法是两次 stable_sort：

// ❌ 错！第二次会破坏第一次的部门内顺序
std::stable_sort(..., [](auto a, auto b) { return a.hire_year < b.hire_year; });
std::stable_sort(..., [](auto a, auto b) { return a.dept < b.dept; });

正确姿势是一次写全比较逻辑：

std::stable_sort(data.begin(), data.end(), [](const auto& a, const auto& b) {
    if (a.dept != b.dept) return a.dept < b.dept;
    return a.hire_year < b.hire_year; // 同部门内按年份排
});

stable_sort 的稳定性，只保障“相等元素的原始相对顺序”，不保障跨次调用的累积效果。

还有一个容易踩的坑：并行 stable_sort 会申请 O(n) 临时内存。如果 data 占用 800MB，它可能瞬间多吃 800MB——在嵌入式或内存受限服务里，这比慢还致命。此时要么降级用单线程版，要么手动预分配缓冲区（标准没提供接口，但你可以自己 std::vector<T> temp(data.size()) 然后 std::inplace_merge 分段处理）。

最后说个冷知识：stable_sort 在小数组上会自动切回插入排序。GCC 实现里，子区间长度 ≤ 32 时直接插排——它连“小到不用并行”的判断都帮你做了。你不需要手写阈值判断，只要数据结构支持随机访问迭代器（vector、deque 行，list 不行），它就自己权衡。

所以，下次遇到需要保序的批量排序，别条件反射写 sort 再加一堆索引映射。试试 stable_sort，加个 execution::par_unseq，再检查下比较函数是否纯。它不炫技，不堆概念，就安静地把该稳的稳住，该快的加快。就像厨房里那把厚背刀——不声不响，但剁骨、切片、片鱼生，样样不拖泥带水。