图论：合并网络

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

合并网络基于以下假设：

给定两个排序的序列, 如果我们颠倒第二个序列的顺序, 然后连接两个序列, 则得到的序列是双音调的。

例如：给定两个已排序的零一序列X = 00000111和Y = 00001111, 我们将Y反转以获得YR =11110000。将X和YR串联可得到0000011111110000, 这是双音调的。

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

给定SORTER的深度[n]

谁的解是D（n）=θ（log2n）。因此, 我们可以在ₒ（log2n）时间内并行排序n个数字。