哪种排序方法最适合并行处理？

Question

我现在正在查看我的旧学校作业,并希望找到问题的解决方案.

哪种排序方法最适合并行处理？

1. 冒泡排序
2. 快速排序
3. 合并排序
4. 选择排序

我想快速排序(或合并排序？)就是答案.

我对么？

Answer 1

与合并排序一样,快速排序也可以轻松并行化,因为它具有分而治之的特性.单个就地分区操作难以并行化,但是一旦划分,列表的不同部分可以并行排序.

并行快速排序优于其他并行排序算法的一个优点是不需要同步.一旦子列表可供其工作,就会启动新线程,并且它不与其他线程通信.当所有线程完成后,排序就完成了.

http://en.wikipedia.org/wiki/Quicksort

Answer 2

它完全取决于并行化的方法.对于多线程通用计算,合并排序提供了非常可靠的负载平衡和内存本地化属性.对于硬件中的大型分拣网络,如果您需要良好的O(log²n)性能,则实际上最好采用Batcher,Bitonic或Shell排序形式.