归并排序中如何多线程进行归并操作？

Question

在我见过的合并排序的多线程版本中，多线程通常是在左右子数组的递归过程中完成的（即，每个线程都被分配了自己的子数组来处理），并且合并操作是由每个线程完成各自的工作后主线程。

我想知道是否有一种好方法可以对要合并 2 个已排序子数组的最终合并操作进行多线程处理？如果是这样，该怎么办？

Answer 1

实际上有一种方法可以将合并任务拆分到2个并发线程中：

• 一旦两个子数组都排序完毕，
• 分配一个线程任务，将已排序子数组开头的元素合并到目标数组的前半部分，并且
• 为另一个线程分配一个不同但互补的任务：从末尾开始，从已排序子数组的末尾合并到目标数组的后半部分。
• 您必须仔细编写这些合并函数，以便排序保持稳定，并且每个线程应该只写入目标数组的一半，可能会从已排序的子数组中读取相同的元素，但选择不同的元素。

我还没有在有关多线程归并排序的文献中看到过这种方法。我想知道它的性能是否比经典实现更好。

Answer 2

排序数组的合并可以分为 n 个独立的、可并行的任务。总体思路是从输入数据中选取值，并在自己的线程中合并这些值之间的子数组元素。步骤是：

1. 从未排序的输入数据中选取 n - 1 个值
2. 正常合并排序，直到子数组足够大，值得在多个线程中合并。
3. 对于要合并的每个子数组，对于您选择的每个值，查找该值最后一次出现的索引（如果存在），或者查找比该值高的第一个值（如果不存在）的索引。
4. 对每个索引列表进行排序，并将子数组的开头和结尾放入列表中。
5. 您现在可以合并从索引 i（含）到索引 i+1（不包括）的每个子数组的切片，并将结果写入磁盘，与合并的其余部分无关。

这是一个具体的例子：

unsorted input:  [a,w,d,y,u,p,l,s,c,e,g,h]
pick values: g and p
subarrays in last step of mergesort: a = [a,d,p,u,w,y] and b = [c,e,g,h,l,s] 
indexes of picked values (or next highest) in a: a_ind=[2, 2]
indexes of picked values (or next highest) in b: b_ind=[2, 5]
add ends of array to indexes: a_ind=[0,2,2,6], b_ind=[0,2,5,6]

merge each of these in separate threads:
[a,d] with [c,e]
[] with [g, h, l]
[p,u,w,y] with [s]

这个例子效率很低，但根据我的经验，如果子数组很大并且你仔细选择n，它可以提供良好的并行化和更快的排序。

您可以在其他结果完成之前将单个线程的结果写入输出文件，因为您知道它从 a_ind[i] + b_ind[i] 开始，以及您在该线程上合并了多少个值。

一个挑战是找到一种平均分配工作的方法。我随机选择了值，并且选择了比我拥有的核心多得多的值，这对于在线程之间均匀分配工作非常有效。

这实际上只是 @chqrlie 答案的概括，但希望它可以帮助某人。