在串行情况下，排序需要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年更新： 这是大约在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上针对大型数据集的排序：彻底的比较
