algorithm - 使用二进制搜索的并行合并排序

Question

我正在尝试在 Designing Efficient Sorting Algorithms for Manycore GPUs 中提到的 CUDA 上实现合并排序算法.

对于中级，它建议分配一个线程 block 以将两个排序数组(比如 A 和 B)合并到一个数组。这个想法是为数组 A 上的数据 - a_i 分配一个线程，并使用二进制搜索在 B 数组上找到它的位置。如果 a_i 在 B 上的位置是 j 则 a_i 在新数组上的位置是 (i+j)

但是当我实现这个(或尝试实现)时，我发现上面的方法似乎不起作用。比如需要合并的两个数组如下，

和

所以第一个数组(灰色阴影部分)上的 53 会发现它在第二个数组上的相应位置是 11，所以它在最终数组上的位置是 (11 + 11 = 22)。同样，53 在蓝色阴影的第一个数组中的位置是 (11 + 12 = 23)。

如果我们取第二个数组的 53，它的最终位置也给出为 (11 + 11 = 22)。这与第一个阵列上的灰色 53 冲突。

所以根据我的理解，不能使用简单的二分查找算法来合并这两个数组。是否有已知或更简单的方法来解决此冲突？

Answer 1

在论文中，我读到:

Given the sorted sequences A and B, we want to compute the sorted sequence C = merge(A, B). If these sequences are sufficiently small, say of size no greater than t = 256 elements each, we can merge them using a single t-thread block. For an element ai ∈ A, we need only compute rank(ai , C), which is the position of element ai in the merged sequence C. Because both A and B are sorted, we know that rank(ai , C) = i + rank(ai , B), where rank(ai , B) is simply the count of elements bj ∈ B with bj < ai and which we compute efficiently using binary search. Elements of B can obviously be treated in the same way.

当您寻找 rank(ai, B) 时，您必须在二分查找中处理重复项。将 B 想象成一个 BST，rank(ai, B) = max of j {bj <= ai} +1 应该效果很好。