双调排序网络

单调递增然后单调递减，或者单调递减然后单调递增的序列称为双调序列。 例如：序列 (2, 5, 6, 9, 3, 1) 和 (8, 7, 5, 2, 4, 6) 都是双调序列。 双调排序器是一个比较网络，用于对 0 和 1 的双调序列进行排序。

半清洗器：双调排序器包含几个阶段，每个阶段称为半清洗器。每个半清洗器是一个深度为 1 的比较网络，其中输入线 i 与线 1+ 进行比较，对于 i = 1, 2.....。

当将 0 和 1 的双调序列作为输入传递给半清洗器时，半清洗器产生一个输出序列，其中较小的值位于上半部分，较大的值位于下半部分，并且两半都是双调的，并且至少有一半是干净的。

双调排序器：通过递归地连接半清洗器，我们可以构建一个双调排序器，它是一个对双调序列进行排序的网络。 BITONIC-SORTER [n] 的第一阶段由 HALF-CLEANER [n] 组成，它产生两个大小减半的双调序列，使得上半部分的每个元素都至少与下半部分的每个元素一样小。 因此，我们可以通过递归地使用两个 BITONIC-SORTER [n/2] 的副本来对两半进行排序来完成排序。

图：BITONIC-SORTER [n] 的深度 D (n) 由递推给出，其解为 D (n) = log n。