哪种并行sortingalgorithm具有最好的平均情况下的性能？
在序列情况下sorting需要O（n log n）。 如果我们有O（n）处理器，我们希望线性加速。 O（log n）并行algorithm存在，但它们具有很高的常数。 它们也不适用于在O（n）处理器附近没有任何地方的商品硬件。 对于p处理器，合理的algorithm应该花费O（n / p log n）时间。
在序列情况下，快速sorting平均具有最佳的运行时复杂性。 并行快速sortingalgorithm很容易实现（见这里和这里 ）。 然而，由于第一步是将整个集合分割到单个内核上，因此性能不佳。 我已经find许多并行sortingalgorithm的信息，但到目前为止我还没有看到任何指向明确的赢家。
我正在寻找以8到32个核心运行的JVM语言sorting100万到1亿个元素的列表。
以下文章（PDF下载）是各种体系结构上并行sortingalgorithm的比较研究：
在各种体系结构上的并行sortingalgorithm
根据文章， 样本sorting似乎是许多并行架构types中最好的。
更新以解决Mark对年龄的关注：
这里有更近期的文章介绍更新颖的东西（从2007年，顺便说一句，仍然得到比较样本sorting）：
样品分类改进
AA-sorting
出血的边缘（大约在2010年，一些只有几个月大）：
并行sorting模式
基于GPU的多核并行sorting
混合CPU / GPU并行sorting
随机并行sortingalgorithm的实验研究
高度可扩展的并行sorting
使用自然顺序sortingN元素：一种新的自适应sorting方法
2013年更新：大约在2013年1月份，这里是出血点。（注：一些链接是在Citeseer的文件，需要注册是免费的）：
大学讲座：
并行分区select和sorting
并行sortingalgorithm讲座
并行sortingalgorithm讲座2
并行sortingalgorithm讲座3
其他来源和论文：
基于自适应比特sorting的多核体系结构分类algorithm
高度可扩展的并行sorting2
并行合并
并行合并2
并行对象自动sorting系统
序列快速sorting与并行快速sortingalgorithm的性能比较
共享内存，消息传递和混合合并sorting用于独立和群集SMP
各种并行algorithm（sorting等）包括实现
GPU和CPU / GPU混合来源和论文：
一种用于GPU架构的并行sortingalgorithm的OpenCL方法
数据分类使用graphics处理单元
在GPU上进行sorting的高效algorithm
为许多GPUdevise高效的sortingalgorithm
针对GPU的确定性样本分类
基于双向sorting的CUDA快速就地分拣
使用混合algorithm的快速并行GPU分类
GPU上的快速并行sortingalgorithm
在CPU和GPU上快速sorting：带宽不经意SIMDsorting的情况
GPU样本sorting
GPU-ABiSort：stream体系结构上的最佳并行sorting
GPUTeraSort：用于大型数据库pipe理的高性能graphics协处理器分类
基于高性能比较的多核GPUsortingalgorithm
对支持CUDA的GPU进行并行外部sorting，具有负载平衡和低传输开销
在GPU上进行大规模数据集sorting：彻底比较
我已经使用了并行快速sortingalgorithm和PSRSalgorithm，它们基本上将QuickSort与合并并行。
使用并行快速sortingalgorithm，我已经演示了多达4个内核（具有超线程的双核）的接近线性加速，由于该algorithm的局限性，我们预计这是预期的。 纯粹的并行快速sorting依赖共享堆栈资源，这将导致线程之间的争用，从而降低性能的增益。 这个algorithm的优点是它能够“就地”sorting，从而减less了所需的内存量。 如您所述，您可能需要考虑这个问题时，将100M元素sorting。
我看到你正在寻找一个8-32核心的系统sorting。 PSRSalgorithm避免了在共享资源上的争用，允许在更多的进程中加速。 我已经演示了多达4个核心的algorithm，但是其他的实验结果报道了线性加速，32核心以及更多的核心。 PSRSalgorithm的缺点是它不在位，并且需要相当多的内存。
如果你有兴趣，你可以使用或仔细阅读我的Java代码中的每一种algorithm。 你可以在github上find它： https ： //github.com/broadbear/sort 。 该代码旨在作为Java Collections.sort（）的简单replace。 如果您正在寻找能够在JVM中执行并行sorting的function，则可以使用我的回购代码中的代码。 该API是完全通用的元素实现Comparable或实现自己的比较器。
请问您在寻找什么样的元素来分类？ 我很想知道我的分类软件包的潜在应用程序。
看看这篇文章： 一种使用精确分割的可伸缩并行sortingalgorithm 。 它涉及到多于32个内核。 然而，它详细描述了一个algorithm，其运算时间复杂度为O（n / p * log（n）+ p * log（n）** 2），适用于任意的比较器。
论文“不同架构上的并行sortingalgorithm的比较”可能是一个很好的开始。
