algorithm - 哪种并行排序算法具有最好的平均情况性能？

Question

在串行情况下，排序需要 O(n log n)。如果我们有 O(n) 个处理器，我们希望线性加速。 O(log n) 并行算法存在，但它们具有非常高的常数。它们也不适用于没有接近 O(n) 处理器的商品硬件。对于 p 个处理器，合理的算法应该花费 O(n/p log n) 时间。

在串行情况下，快速排序平均具有最佳的运行时复杂度。并行快速排序算法很容易实现(参见 here 和 here )。然而，它表现不佳，因为第一步是将整个集合分区在一个核心上。我找到了许多有关并行排序算法的信息，但到目前为止，我还没有看到任何指向明确赢家的信息。

我希望使用运行在 8 到 32 个内核上的 JVM 语言对包含 100 万到 1 亿个元素的列表进行排序。

Answer 1

下面这篇文章(PDF下载)是各种架构上并行排序算法的对比研究:

Parallel sorting algorithms on various architectures

根据这篇文章，样本排序 似乎在许多并行架构类型上是最好的。

更新以解决马克对年龄的担忧:

这里有更多最近的文章介绍了一些更新颖的东西(从 2007 年开始，顺便说一句，仍然与样本排序进行比较):

Improvements on sample sort
AA-Sort

前沿(大约 2010 年，有些只有几个月):

Parallel sorting pattern
Many-core GPU based parallel sorting
Hybrid CPU/GPU parallel sort
Randomized Parallel Sorting Algorithm with an Experimental Study
Highly scalable parallel sorting
Sorting N-Elements Using Natural Order: A New Adaptive Sorting Approach

2013 年更新:这是大约 2013 年 1 月的最前沿。(注意:一些链接指向 Citeseer 上的论文，需要免费注册):

大学讲座:
Parallel Partitioning for Selection and Sorting
Parallel Sorting Algorithms Lecture
Parallel Sorting Algorithms Lecture 2
Parallel Sorting Algorithms Lecture 3

其他来源和论文:
A novel sorting algorithm for many-core architectures based on adaptive bitonic sort
Highly Scalable Parallel Sorting 2
Parallel Merging
Parallel Merging 2
Parallel Self-Sorting System for Objects
Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms
Shared Memory, Message Passing, and Hybrid Merge Sorts for Standalone and Clustered SMPs
Various parallel algorithms (sorting et al) including implementations

GPU 和 CPU/GPU 混合源和论文:
An OpenCL Method of Parallel Sorting Algorithms for GPU Architecture
Data Sorting Using Graphics Processing Units
Efficient Algorithms for Sorting on GPUs
Designing efficient sorting algorithms for manycore GPUs
Deterministic Sample Sort For GPUs
Fast in-place sorting with CUDA based on bitonic sort
Fast parallel GPU-sorting using a hybrid algorithm
Fast Parallel Sorting Algorithms on GPUs
Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort
GPU sample sort
GPU-ABiSort: Optimal Parallel Sorting on Stream Architectures
GPUTeraSort: high performance graphics co-processor sorting for large database management
High performance comparison-based sorting algorithm on many-core GPUs
Parallel external sorting for CUDA-enabled GPUs with load balancing and low transfer overhead
Sorting on GPUs for large scale datasets: A thorough comparison

2022 年更新:我没有忘记这个答案，就像所有与计算机相关的东西一样，它还没有很好地老化。我将尽我所能在今年年底(2022 年)之前的某个时候根据当前趋势和最新技术对其进行更新和更新。如果您对此主题感兴趣并希望尽快看到更新，请回复或更好地为我在该答案下方发表的评论点赞，以便我可以评估对此主题的兴趣其他也需要更新。