C++17 之后，std::sort 真的“并行”了吗？别急着开 std::execution::par

你是不是也遇到过这样的场景：处理上百万条订单数据时，std::sort(vec.begin(), vec.end()) 耗时 320ms；加了 #include <execution>，改成 std::sort(std::execution::par, ...)，结果一跑——程序卡住、结果错乱、甚至直接崩溃？不是代码写错了，是没搞清“并行 sort”在 C++ 标准里的真实边界。

C++17 引入了并行算法库，std::sort 确实支持 std::execution::par 和 std::execution::par_unseq 两种策略。但这里有个关键事实被很多教程悄悄跳过了：标准只要求“实现可选择支持”，并不强制要求提供并行版本。换句话说，GCC libstdc++ 直到 11.4 才实验性加入（需手动启用 _GLIBCXX_PARALLEL），而 MSVC 的 STL 直到 VS2022 17.5 才开始稳定支持 par，且默认仍走串行路径。Clang + libc++？至今未实现并行 sort —— 它会静默退化为串行，连警告都不给。

所以，第一件事不是改代码，而是先确认你的工具链是否真能并行。一个简单验证法：

auto start = std::chrono::steady_clock::now();
std::sort(std::execution::par, data.begin(), data.end(), [](auto& a, auto& b) {
    std::this_thread::sleep_for(1ns); // 避免优化掉
    return a.id < b.id;
});
auto dur = std::chrono::steady_clock::now() - start;
// 对比串行耗时。若两者几乎一致，说明并行未生效。

真正起效的，并不是 std::sort 本身，而是底层实现是否挂钩了 OpenMP 或 TBB。比如 GCC 启用 -fopenmp -D_GLIBCXX_PARALLEL 后，par 才会触发分治+多线程快排；而 MSVC 默认依赖其内部线程池，无需额外链接。没有配套运行时支持，“par” 就是个无效标记。

那如果手头是 Clang 或旧版 GCC，又确实需要提速？别硬等标准库——自己搭个轻量级并行快排更实在。核心思路就三点：

• 递归深度控制：超过阈值（如 log2(n) * 2）就切到串行，避免线程创建开销反超收益；
• 分区后异步处理子区间：用 std::async 或线程池分发左右段，但注意不能共享迭代器或容器内存（vector 可能 realloc）；
• pivot 选取防退化：别用首/尾元素，改用三数取中 + 随机扰动，尤其对部分有序数据效果明显。

下面是一段可直接粘贴的实用实现（仅依赖 C++17）：

#include <algorithm>
#include <future>
#include <thread>

template<typename It, typename Comp = std::less<>> 
void parallel_sort(It first, It last, Comp comp = {}) {
    const size_t threshold = 8192; // 实测在多数机器上收益拐点
    if (last - first <= static_cast<ptrdiff_t>(threshold)) {
        std::sort(first, last, comp);
        return;
    }

    // 三数取中选 pivot，避免最坏 O(n²)
    auto mid = first + (last - first) / 2;
    if (comp(*mid, *first)) std::iter_swap(mid, first);
    if (comp(*last-1, *first)) std::iter_swap(last-1, first);
    if (comp(*last-1, *mid)) std::iter_swap(last-1, mid);
    std::iter_swap(mid, last-1);

    // Lomuto 分区（简洁易懂，实际项目可用 Hoare 版减 swap 次数）
    auto pivot = *(last-1);
    auto i = first;
    for (auto j = first; j != last-1; ++j) {
        if (comp(*j, pivot)) {
            std::iter_swap(i++, j);
        }
    }
    std::iter_swap(i, last-1);

    // 异步处理左右两段，但注意：必须确保 vector 不在排序中扩容！
    // 所以调用前建议 vec.reserve(vec.size());
    if (i - first > threshold && last - (i+1) > threshold) {
        auto fut = std::async(std::launch::async, 
            [first, i, comp] { parallel_sort(first, i, comp); });
        parallel_sort(i+1, last, comp);
        fut.wait();
    } else {
        parallel_sort(first, i, comp);
        parallel_sort(i+1, last, comp);
    }
}

这段代码没用任何第三方库，却比盲目开 std::execution::par 更可控。它把并行粒度攥在自己手里：小数组不折腾线程，大数组才分发，且 pivot 稳定——这才是工程中真正可落地的“并行加速”。

最后提醒一句：并行不是银弹。如果你的比较函数里有锁、IO 或复杂对象拷贝，开多线程反而更慢。实测中，纯数值排序提升 2–3 倍很常见；但若 comp 里调了 std::string::compare 或 std::sqrt，收益可能只剩 1.2 倍，甚至倒挂。速度瓶颈从来不在 CPU 核数，而在数据访问模式和操作复杂度。

下次再看到“C++17 并行算法”的宣传，不妨先 nm -C libstdc++.so | grep sort_par 看一眼符号是否存在。标准写得漂亮，落地还得看编译器敢不敢扛、runtime 愿不愿配、你自己愿不愿意拆开看看——毕竟，真正的并行，从来不在头文件里，而在你敲下每一行代码时的清醒判断。