如何在合并排序中对合并操作进行多线程处理？

Question

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

我想知道在合并 2 个已排序子数组的情况下是否有一种多线程处理最终合并操作的好方法？如果可以，如何实现？

Answer 1

实际上有一种方法可以在 2 个并发线程之间拆分合并任务：

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

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