双调的排序网络

单调增加然后单调减少, 或者单调减少然后单调增加的序列称为双音序列。例如：序列（2、5、6、9、3、1）和（8、7、5、2、4、6）都是双声的。双音分类器是一个比较网络, 可对0和1的双音序列进行分类。

Half-Cleaner：双音速分选机包含多个阶段, 每个阶段都称为Half-cleaner。每个半清洁器都是深度为1的比较网络, 其中对于i = 1、2 …, 将输入线i与线1+进行比较。

当将0和1的双音序列用作半清洁器的输入时, 半清洁器会产生一个输出序列, 其中较小的值在上半部, 较大的值在下半部, 并且两个半部都是双音的, 并且至少一半是干净的。

Bitonic Sorter：通过递归连接半清洁器, 我们可以构建一个Bitonic Sorter, 这是一个对Bitonic序列进行排序的网络。 BITONIC-SORTER [n]的第一级由HALF-CLEANER [n]组成, 它会产生两个大小为一半的双音序列, 以使上半部分的每个元素至少与下半部分的每个元素一样小。因此, 我们可以通过使用BITONIC-SORTER [n / 2]的两个副本来对两个半部分进行递归排序来完成排序。

图：BITONIC-SORTER [n]的深度D（n）由递归给出, 其解为D（n）= log n。