合并网络

合并网络是可以将两个已排序的输入序列合并成一个已排序的输出序列的网络。 我们采用 BITONIC-SORTER [n] 来创建合并网络 MERGER [n]。

合并网络基于以下假设

给定两个已排序的序列，如果我们反转第二个序列的顺序，然后连接这两个序列，则结果序列是双调的。

例如：给定两个已排序的零一序列 X = 00000111 和 Y = 00001111，我们反转 Y 得到 Y^R = 11110000。 级联 X 和 Y^R 产生 0000011111110000，它是双调的。

排序网络 SORTER [n] 需要合并网络来实现并行版本的合并排序。 SORTER [n] 的第一阶段由 n/2 个 MERGER [2] 的副本组成，它们并行工作以合并一对 1 元素序列，以产生长度为 2 的已排序序列。 第二阶段由 n/4 个 MERGER [4] 的副本组成，这些副本将这些 2 元素已排序序列的对合并，以生成长度为 4 的已排序序列。 通常，对于 k = 1, 2..... log n，第 k 阶段由 n/2^k 个 MERGER [2^k] 的副本组成，它们合并 2^k-1 元素已排序序列的对以产生长度为 2^k 的已排序序列。 在最后阶段，将生成一个由所有输入值组成的已排序序列。 可以通过归纳证明，该排序网络可以对零一序列进行排序，因此，根据零一原则，它可以对任意值进行排序。

给定 SORTER [n] 的深度的递归

其解为 D (n) = θ (log²n)。 因此，我们可以并行地在 ₒ (log²n) 时间内对 n 个数字进行排序。