哪种并行排序算法具有最佳的平均案例性能？
在串行情况下，排序需要O（n log n）。如果我们有O（n）个处理器，我们希望线性加速。存在O（log
n）并行算法，但是它们具有很高的常数。它们也不适用于没有O（n）处理器的商品硬件。对于p个处理器，合理的算法应花费O（n / p log n）时间。
在串行情况下，快速排序平均具有最佳的运行时复杂性。并行快速排序算法易于实现。但是，由于最初的步骤是将整个集合分区在单个内核上，因此执行效果并不理想。我发现了许多并行排序算法的信息，但到目前为止，我还没有发现任何指向明确赢家的信息。
我正在寻找一种在8到32个内核上运行的JVM语言中100万到1亿个元素的列表的排序方式。
回答：
以下文章（PDF下载）是对各种体系结构上的并行排序算法的比较研究：
各种架构上的并行排序算法
根据这篇文章， 似乎在许多并行体系结构类型上都是最好的。
更新以解决Mark对年龄的关注：
以下是一些较新的文章，介绍了一些更新颖的内容（从2007年开始，顺便说一下，仍然可以与样本排序进行比较）：
样品分类 AA-
排序的改进
前沿（大约在2010年，有些才几个月）：
并行排序模式
基于多核GPU的并行排序
混合CPU / GPU并行排序
带有实验研究的随机并行排序算法使用自然顺序对N元素进行
高度可扩展的并行排序
排序：一种新的自适应排序方法
这是大约在2013年1月的前沿。（注意：一些链接是Citeseer上的论文，需要免费注册）：
大学讲座：
用于选择和排序的并行分区
并行排序算法讲座
并行排序算法讲座2
并行排序算法讲座3
其他来源和论文：
基于自适应双音排序的多核体系结构的新颖排序算法
高度可扩展的并行排序2
并行合并
并行合并对象的2个
并行自排序系统
顺序快速排序和并行快速排序算法的性能比较
独立和群集SMP的共享内存，消息传递和混合合并排序
各种并行算法（排序等），包括实现
GPU和CPU / GPU混合来源和论文： 使用图形处理单元
对GPU体系结构进行
数据排序的并行排序算法的OpenCL方法
在GPU上进行
高效排序的算法在许多核GPU
上设计高效的排序算法为GPU进行
确定性样本排序使用GPU进行
快速就地排序基于双比特排序的CUDA
使用混合算法的
快速并行GPU
排序在GPU
上的快速并行排序算法在CPU和GPU
上的快速排序：带宽不考虑SIMD排序的情况
GPU样本排序
GPU-ABiSort：流架构上的最佳并行排序
GPUTeraSort：高用于大型数据库管理的性能图形协处理器排序
多核GPU上基于高性能基于比较的排序算法，
具有负载平衡和低传输开销的支持CUDA的GPU的并行外部
排序在GPU上针对大型数据集的排序：彻底的比较
以上是 哪种并行排序算法具有最佳的平均案例性能？ 的全部内容， 来源链接： utcz.com/qa/408645.html
