我想为家庭作业实现一种快速算法，但是为此任务使用并行处理。我听说Quicksort的并行版本是最好的选择，但是我不确定这一点……也许Heapsort是个好主意。您认为哪种算法最适合并行化环境，为什么？
快速排序可以将未排序的列表分为两半，但是不幸的是，不能保证这两个半数几乎相等。因此，一台计算机（或一组计算机的一半）可以获取20个条目，另一半可以获取200亿个条目。
合并排序是一种出色的并行排序技术。最佳分类始终取决于机器，并且通常涉及针对不同大小输入的分类技术的组合。
作为Dean J mentions，合并排序是一个不错的选择。但是它的缺点是两个线程都完成时需要同步（合并过程）。
如何分两步考虑。
[步骤1.将我的数据细分为N个块，其中N是我的处理器/节点/核心数。对每个块进行排序。
您应考虑Bitonic Sort：
此算法有点类似于合并排序，但是它有一个有趣的变化：不是将数组的两半从低到高排序，然后合并，而是在相反方向
快速排序是递归的，使任何递归算法并行的一种简单方法（仅当它涉及到两个或多个递归调用时（如quicksort一样））是为递归调用生成两个新线程，并等待它们完成，然后完成您的功能。这绝不是最佳选择，但它是并行化递归调用的一种相当快捷且肮脏的方法。
我实际上为前一个并行化库研究了一种并行排序算法，并得出结论认为这样做不值得。对于小型数据集，即使是几个同步原语的代价也使并行排序比常规排序慢。对于大型数据集，您通常受共享内存带宽的束缚，并且获得的加速极小。对于排序大量（我认为是1000万）整数的情况，使用并行快速排序IIRC，我只能在双核上获得<1.5倍的加速。]
编辑：
[我做的大部分编程都是数字运算，所以我倾向于考虑对简单基元进行排序。对于这些情况，我仍然认为并行排序是个坏主意。但是，如果您要排序比较昂贵的事物，则此答案不适用。