C++如何实现多线程排序算法-C++-PHP中文网

c++oding="utf-8" ?>

std::sort非线程安全，多线程并发排序同一容器会触发未定义行为；正确做法是分段独立排序后用std::inplace_merge合并，需注意稳定性与性能阈值。

c++如何实现多线程排序算法

std::sort 本身不是线程安全的，别直接并发调用

多个线程同时对同一块 std::vector 调用 std::sort 会触发未定义行为——底层可能重用缓冲区、修改内部迭代器状态，甚至崩溃。这不是“偶尔出错”，而是只要数据地址重叠就大概率崩，尤其在 GCC libstdc++ 或 MSVC STL 中常见报错如 __glibcxx_assert 失败或段错误。

正确做法是：每个线程处理互不重叠的数据段。比如把一个大数组切分成 N 块，每块独立排序：

std::vector<int> data = {/* ...百万级数据... */};
const size_t n_threads = 4;
const size_t chunk_size = data.size() / n_threads;
<p>std::vector<:thread> threads;
for (size_t i = 0; i </:thread></p>
<h3>合并已排序子段要用 std::inplace_merge，不是手写归并</h3>
<p>分段排序完，必须把相邻有序段合并成整体有序。别自己循环比大小再拷贝——容易越界、漏元素、性能差。C++ 标准库提供 <code>std::inplace_merge</code>，原地完成两段有序区间的归并，时间复杂度 O(n)，且复用已有内存。</p>
<p>注意它只接受三个迭代器：<code>[first, middle)</code> 和 <code>[middle, last)</code> 必须各自有序，函数会把整个 <code>[first, last)</code> 变成有序：</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）"><img
														src="https://img.php.cn/upload/manual/000/000/001/5d6de31fedca2993.png" alt="C函数速查手册（CHM版）" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）" class="overflowclass">C函数速查手册（CHM版）</a>
													<p class="overflowclass">C函数速查手册（CHM版）</p>
												</div>
												<a rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>
<ul>
<li>合并前确保每段已排好（上一步 done）</li>
<li>从最小粒度开始合并：先合第0&1段，再合结果与第2段，依此类推</li>
<li>若想并行合并（如树形归并），需额外同步，但通常单线程 <code>std::inplace_merge</code> 已足够快</li>
</ul>
<p>示例（接上）：</p>
<pre class="brush:php;toolbar:false;">// 合并第0段和第1段
std::inplace_merge(data.begin(), data.begin() + chunk_size, data.begin() + 2 * chunk_size);
// 再合并前两段结果与第2段
std::inplace_merge(data.begin(), data.begin() + 2 * chunk_size, data.begin() + 3 * chunk_size);
// ...以此类推，或用循环

std::stable_sort 比 std::sort 更适合多线程分段场景

如果原始数据含等值元素且需保持相对顺序（比如按 ID 排序时，相同分数的学生要按录入顺序排），std::sort 不保证稳定性，而 std::stable_sort 在多数实现中采用归并策略——这恰好契合分段排序+归并的天然结构。

实测差异：

libstdc++ 的 std::stable_sort 默认就是分段+归并，你手动分段后调用它，反而可能绕过其内部优化
更稳妥的做法：直接对整段调用 std::stable_sort，它内部已做并行化尝试（GCC 11+、Clang 14+ 启用 -D_GLIBCXX_PARALLEL 时）
若坚持手动并行，仍用 std::sort 分段 + std::inplace_merge，但最终结果不保稳定；需要稳定，就在合并阶段用 std::merge 到临时 buffer，再拷回

别忽略小数组退化问题和线程开销阈值

启动 8 个线程去排序 1000 个 int，大概率比单线程慢——线程创建/同步/缓存失效的开销远超排序本身。实际中需设置合理阈值：

总元素数 std::sort 单线程
总元素数 ≥ 10⁵：才考虑分段并行，且线程数 ≤ CPU 物理核心数（std::thread::hardware_concurrency()）
每段长度 std::sort 的插入排序优化还没起效，性能波动大

另外，C++20 的 std::ranges::sort 支持执行策略（如 std::execution::par_unseq），但依赖标准库实现是否真正并行——MSVC 目前仅对 std::sort 做了有限并行，libstdc++ 需手动开启 parallel mode。别以为写了 par_unseq 就一定多线程跑。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！