排序在串行情况下需要O(n log n).如果我们有O(n)处理器,我们希望线性加速.存在O(log n)并行算法,但它们具有非常高的常数.它们也不适用于没有O(n)处理器附近的商品硬件.对于p个处理器,合理的算法应该花费O(n/p log n)时间.
在串行的情况下,快速排序平均具有最佳的运行时复杂性.并行快速排序算法易于实现(请参见此处和此处).但是它表现不佳,因为第一步是将整个集合划分到单个核心上.我已经找到了许多并行排序算法的信息,但到目前为止我还没有看到任何指向明显赢家的信息.
我希望在运行8到32个内核的JVM语言中对100万到1亿个元素的列表进行排序.