本文介绍一种并行排序算法实现,
基本原理非常简单,
将数据按照顺序切片,每个片段分配给一个单独的线程处理。
单个片段可以使用常规的排序算法。
每个片段排序好,之后,进行归并运算,
每一级的归并也可以用多线程并行处理。
以8个片段为例;
(1,2),(3,4),(5,6),(7,8)分别归并;
形成4个片段,1,2,3,4;
然后(1,2)(3,4)归并形成1,2
最后合并为1个;
下面给出代码链接:
https://github.com/wiltchamberian/Algorithms/blob/main/PSort.h
经不完全测试,100万量级,平均速度高于c++17的并行排序算法。代码只依赖c++11.