将小数组排序为大型排序数组

您可以实现基于块的算法来有效地解决此问题（无论数组的输入大小如何，只要一个数组比另一个小得多）。

首先，您需要对小数组进行排序（如果您不需要自定义比较器，则可以使用基数排序或位排序）。 然后，我们的想法是将大数组切成完全适合 CPU 缓存的块（例如 256 KiB）。 对于每个块，使用二进制搜索查找小数组 <= 到块最后一项的最后一项的索引。 这相对较快，因为小数组可能适合缓存，如果数组很大，则在连续的块之间获取二进制搜索的相同项。 通过此索引，您可以知道在写入之前需要将多少个项目与块合并。 对于要合并到块中的每个值，请使用块中的二进制搜索查找值的索引。 这很快，因为块适合缓存。 一旦知道要插入到块中的值的索引，就可以有效地在每个块中逐块移动项目（可能从末尾到开头就地移动）。 这种实现比传统的合并算法快得多，因为由于二进制搜索和块插入的项目数量很少，因此所需的比较数量要少得多。

对于相对较大的输入，可以使用并行实现。这个想法是同时处理一组多个块（即超级块）。 超级块比经典块大得多（例如 >=2 MiB）。 每个线程一次处理一个超级块。对小数组执行二进制搜索，以了解每个超级块中插入了多少个值。 这个数字在线程之间共享，以便每个线程知道它可以独立于其他线程安全地写入输出（可以使用并行扫描算法在大规模并行架构上执行此操作）。然后，将每个超级块拆分为经典块，并使用先前的算法独立解决每个线程中的问题。 当小输入数组不适合缓存时，即使在顺序中，这种方法也应该更有效，因为整个小数组中的二进制搜索操作数量将显着减少。

算法的（摊销）时间复杂度与大数组的长度、小数组的长度和块大小有关（为了清楚起见，这里忽略了超级块，但它们只是像常数一样通过常数因子改变复杂度）。O(n (1 + log(m) / c) + m (1 + log(c)))mncc

替代方法/优化：如果您的比较算子很便宜，并且可以使用 SIMD 指令进行矢量化，那么您可以优化传统的合并算法。传统方法非常慢，因为分支（在一般情况下很难预测），也因为它不能轻松/有效地矢量化。但是，由于大数组比小数组大得多，因此传统算法会从大数组中选取大量连续的值，介于小数组之间的值。这意味着您可以选择大数组的 SIMD 块，并将这些值与其中一个小数组进行比较。如果所有 SIMD 项目都小于从小数组中选取的 SIMD 项目，则可以非常高效地一次性写入整个 SIMD 块。否则，您需要写入 SIMD 块的一部分，然后写入小数组的项并切换到下一个数组。最后一项操作显然效率较低，但应该很少发生，因为小数组比大数组小得多。请注意，小数组仍然需要先排序。