数组元素特定排列的算法(通过定期采样进行并行排序)[C++]

Question

我正在通过规则采样算法实现并行排序 described here .我被困在需要将排序的子列表迁移到排序数组的适当位置的位置。问题可以这样表述:只有一个全局数组。该数组已分为 p 个子数组。每个子数组都已排序。确定了 p-1 个全局枢轴元素，并将每个子阵列分为 p 个子子阵列(黄色、红色、绿色)。现在我需要移动那些子子数组，以便具有本地索引 i 的子子数组在线程 i 中(因此它们以颜色相邻并且从左到右的顺序保持不变的方式排序)。

实际上串行算法可以，但我只是不知道如何获得正确的排列。下图显示了 p=3 个线程的情况。黄色表示子数组 0，红色 - 1，绿色 - 2。

子子数组可以有不同的大小。

Answer 1

好吧，看来我没有足够的声誉来评论你的问题，所以我会采取发布答案的方式。

所以让我直截了本地说。你被困在这个算法的第 3 阶段。正确的？

---

这个怎么样:

让我们有 p 个链接的索引列表。让每个进程将索引范围传达给进程 i；当传递索引时，将索引附加到进程 i 的列表中。当所有通信结束后，你将在进程 i 的列表中拥有进程 i 的所有索引。这个列表的节点应该是一个像

这样的数据结构

 Node {
      index
      valueOfIndex
 }

现在，当您填充列表时，也将其值复制到列表中。

完成该过程后。您可以使用其列表 i 为进程 i 重新创建数组。

????