哪个平行排序算法的平均案例表现最好？

下面的文章(PDF 下载)是对不同架构上的并行排序算法的比较研究:

不同体系结构上的并行排序算法

根据本文，样本分类似乎在许多并行体系结构类型上表现最好。

为回应马克对年龄的关注而提供的最新资料:

下面是最近的一些文章，介绍了一些更新颖的东西(从2007年开始，顺便说一下，仍然可以与样本排序进行比较) :

对示例排序的改进
AA-排序

出血点(大约2010年，有些只有几个月大) :

并行排序模式
基于多核 GPU 的并行排序
混合 CPU/GPU 并行排序
随机平行排序算法实验研究
高度可伸缩的并行排序
基于自然顺序的 N 元素排序: 一种新的自适应排序方法

大学讲座:
用于选择和排序的并行分区
并行排序算法讲座
并行排序算法第2课
并行排序算法第3课

其他来源和文件:
基于自适应位元排序的多核架构新排序算法
高度可伸缩的并行排序2
并行合并
并行合并2
并行目标自排序系统
顺序快速排序与并行快速排序算法的性能比较
独立和集群 SMP 的共享内存、消息传递和混合合并排序
各种并行算法(排序等) ，包括实现

图形处理器和中央处理器/图形处理器混合来源和文件:
一种面向 GPU 体系结构的并行排序算法的 OpenCL 方法
使用图形处理单元进行数据排序
基于 GPU 的高效排序算法
设计高效的多核 GPU 排序算法
GPU 的确定性示例排序
基于位元排序的 CUDA 快速就地排序
基于混合算法的 GPU 快速并行排序
基于 GPU 的快速并行排序算法
CPU 和 GPU 上的快速排序: 带宽不受 SIMD 排序影响的情况
GPU 示例排序
流体系结构上的最优并行排序
用于大型数据库管理的高性能图形协处理器排序
基于多核图形处理器的高性能比较排序算法
支持 CUDA 的图形处理器的并行外排序，具有负载平衡和低传输开销
大规模数据集的 GPU 排序: 一个彻底的比较 < br/>

2022年更新 : 我没有忘记这个答案，就像所有与计算机相关的东西一样，它没有老化。在今年年底(2022年)之前的某个时间点，我将尽我所能更新它，以适应当前的趋势和最新的技术状态。如果你对这个话题感兴趣，并希望看到更新更快，请回复或更好，更新 下面是我的回答，这样我就可以衡量对这个话题的兴趣，其他人也需要一个更新。

这篇论文 < a href = “ https://www.research chgate. net/publications/2617157 _ A _ ratio _ of _ Average _ Sorting _ Strategies _ on _ Different _ Architecture”rel = “ nofollow noReferrer”> “在不同的体系结构上并行排序算法的比较 架构”可能是一个很好的起点

看看这篇论文: 使用精确分裂的可扩展平行排序算法。它涉及到32个以上的核心。然而，它详细地描述了一个运行时间复杂度为 O (n/p * log (n) + p * log (n) * * 2)且适用于任意比较器的算法。

我使用过并行快速排序算法和 PSRS 算法，这两种算法实质上将快速排序并行与合并相结合。

使用并行快速排序算法，我已经演示了最多4个核(具有超线程的双核)的近似线性加速比，这是考虑到该算法的局限性所期望的。一个纯粹的并行快速排序依赖于一个共享的堆栈资源，这将导致线程之间的争用，从而减少任何性能的提高。这种算法的优点是它对“就地”进行排序，从而减少了所需的内存量。如您所述，在对100M 以上的元素进行排序时，您可能需要考虑这一点。

我看到你正在寻找一个系统排序8-32核心。PSRS 算法避免了在共享资源上的争用，允许在较高数量的进程上加速。我已经用上面的4个内核演示了这个算法，但是其他人的实验结果显示，在32个内核以及更多内核的情况下，加速比接近线性。PSRS 算法的缺点是它不适合，并且将需要相当多的内存。

如果您感兴趣，可以使用或仔细阅读我的 Java 代码中的每个算法。你可以在 github: https://github.com/broadbear/sort上找到它。该代码旨在作为 JavaCollections.sort ()的插入式替换。如果您正在寻找在 JVM 中执行上述并行排序的能力，那么我的 repo 中的代码可以帮助您。API 完全泛化用于实现 Compaable 或实现您自己的 Compaator 的元素。

我可以问一下你们为什么要对这么多元素进行排序吗？我有兴趣了解我的分类包的潜在应用程序。