多线程应用程序的最佳排序
今天在一次采访中，我收到一个问题，询问您在多线程应用程序中使用哪种排序。它是合并排序还是快速排序。
Today in a interview I have got the question asking which sort you use for multi threaded application.Weather it is a merge sort or quick sort.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您可以将合并排序用于多线程应用程序。
原因：
归并排序将问题分成单独的较小问题（较小的数组），然后将它们合并。这可以在单独的线程中完成。
快速排序对单个数组进行枢轴排序，因此很难在线程之间有效地划分问题。
You use merge sort for multi-threaded applications.
The reason:
Merge sort divides the problem into separate smaller problems (smaller arrays) and then merges them. That can be done in separate threads.
Quick sort does a pivot sort on a single array, so it's harder to divide the problem efficiently between threads.
每个分治算法都可以很容易地并行化。归并排序和快速排序都遵循相同的基本模式，可以并行运行：
它们的不同之处在于，在快速排序中，除法很困难，而合并很简单（无操作）。在合并排序中，情况恰恰相反：划分很简单，而合并则很困难。
如果您实现上述架构，则快速排序实际上更容易并行化，因为您可以忘记合并步骤。对于合并排序，您需要跟踪已完成的并行任务。这会搞砸负载平衡。
另一方面，如果您遵循上述模式，就会遇到一个问题：第一次划分和最后一次合并将仅使用一个处理器，而所有其他处理器都将处于空闲状态。因此，并行这些操作也是有意义的。在这里我们看到，并行化快速排序中的分区步骤比并行化合并排序中的合并步骤要困难得多。
Every divide and conquer algorithm can be quite easily parallelised. Merge sort and quicksort both follow the same basic schema which can be run in parallel:
Where they differ is that in quicksort, the division is difficult and merging is trivial (no operation). In merge sort, it’s the other way round: dividing is trivial and merging is difficult.
If you implement the above schema, quicksort is actually easier to parallelise because you can just forget about the merge step. For merge sort, you need to keep track of finished parallel tasks. This screws up the load balancing.
On the other hand, if you follow the above schema, you’ve got a problem: the very first division, and the very last merging, will only use a single processor and all other processors will be idle. Thus it makes sense to parallelise these operations as well. And here we see that parallelising the partitioning step in quicksort is much harder than parallelising the merge step in merge sort.
合并排序似乎更容易并行化和分发......想一想，您将其分解为可以轻松划分和分发的干净的子问题。但话又说回来，快速排序也是如此。但是，我可能更喜欢使用合并排序来完成它，因为它可能会更容易。
A merge sort seems like it would be easier to parallelize and distribute...think about it, you're breaking it up into clean sub problems that can easily be divided and distributed. But then again, the same is true of quicksort. However, I would probably prefer doing it with merge sort as it would likely be easier.
假设有一个不错的枢轴选择，那么情况并没有那么不同。
子问题对于并行化来说是微不足道的；它们使用（大部分）不相交的内存并且不需要同步，因此实际的区别在于瓶颈：快速排序的初始分区与合并排序的最终合并。忽视并行化将导致许多核心或少数元素的加速效果不佳（这比您想象的要快得多！）。
两种算法都可以有效地并行化。有关一些实验结果和实现细节，请参阅这篇 MCSTL 论文。 MCSTL 是现在的 GNU C++ std-lib 并行模式的基础。
目前尚不清楚哪种算法在所有情况下都会表现更好，因为它取决于数据分布以及交换或比较是否更慢。
Assuming a decent pivot selection, it's not all that different.
Subproblems are trivial to parallelize; they use (mostly) disjoint memory and need no synchronization, so the actual difference lies in the bottlenecks: the initial partition of quick-sort vs. the final merge in merge-sort. Neglecting to parallelize these will result in bad speedups for many cores or few elements (This gets noticeable a lot faster than you might think!).
Both algorithms can be parallelized efficiently. See this MCSTL paper for some experimental results and implementation details. The MCSTL was the base for what is now the GNU C++ std-lib parallel mode.
It's not all clear which algorithm will perform better in all circumstances as it depends on data distribution and about whether swaps or comparisons are slower.
我认为他们正在寻找合并排序作为答案，因为很容易看出如何在线程之间拆分它。尽管另一个评论表明 qsort 也可以分解为更小的问题。可能许多问题可以分解为更小的问题。
有一个关键方面不容忽视。与其他线程通信需要花费大量时间。在创建线程之前，您正在排序的数据集必须很大，或者比较起来非常昂贵，并且在它们之间进行通信将比仅使用单个线程更好。
除此之外，无论哪种方式，都会遇到严重的错误共享问题。让多个线程处理相同的数据（尽管需要通信时间）可能会变慢，因为 CPU 被迫在多个内核之间共享和更新数据。除非您的算法可以正确对齐数据，否则将其传递给各个线程会减慢速度。
I think they are looking for merge-sort as an answer, since it is easy to see how to split this between threads. Though another comment indicates that qsort can also be split into smaller problems. Likely many can be split into smaller problems.
There is one critical aspect that cannot be ignored. Communicating with the other threads takes a lot of time. The data set your are sorting has to be huge, or very expensive to compare, before creating the threads and doing the communication between them will be better than just using a single thread.
Further to this, with any sort, you have a serious problem of false sharing. Having multiple threads work with the same data can (communication time notwithstanding) be slower as the CPU is forced to share and update data between multiple cores. Unless your algorithm can properly align the data, passing it off to various threads will slow it down.