• 可以构造时间复杂度 $O(\log^2 n)$ 的排序网络。
• 比较器有两个输入与两个输出，$x'=\min(x,y),y'=\max(x,y)$ 可以比较两个值并交换，复杂度 $O(1)$，多个比较器可以并行运算。
• 比较网络由比较器和传数值的线路组成，有 $n$ 个输入线路和 $n$ 个输出线路。

// 输入 [4, 3, 2, 1]，第一步后变 [2, 3, 4, 1]，第二步后变 [2, 3, 1, 4]
4 --X-- 2 ----- 2
3 --|-- 3 ----- 3
2 --X-- 4 --X-- 1
1 ----- 1 --X-- 4

• 排序网络是无论输入是什么，输出总是单调递增（不减）的比较网络。
• $0-1$ 原则为，如果一个比较网络对任意 $01$ 的输入都能排序，那么它也能对任意一般的输入进行排序。
• 下面都只讨论数值为 $01$ 的情况。
• 双调序列：先增后减（$000111000$）或先减后增（$111000111$）的序列。
• 半清洁器：输入长度为 $n$（$n$ 是偶数） 的双调序列 $a$，输出两个长度为 $\tfrac n 2$ 的双调序列 $a'_0,a'_1$，满足 $\forall i, a'_0[i]=0$ 或 $\forall i, a'_1[i]=1$（其中一个是清洁的）。只要拿 $n$ 个比较器连接 $a[i]$ 和 $a[i+\tfrac n 2]$ 即可，$O(1)$。

0 --X----------- 0
0 --|--X-------- 0
1 --|--|--X----- 0
1 --|--|--|--X-- 0
1 --X--|--|--|-- 1
0 -----X--|--|-- 0
0 --------X--|-- 1
0 -----------X-- 1

• 双调排序网络：将长度为 $n$ 的双调序列排序。先连一个清洁器，再对两个输出序列都连清洁器，不断重复，$O(\log n)$。

0 --X-------- 0 --X---- 0 --X---- 0
0 --|-X------ 0 --|-X-- 0 --X---- 0
1 --|-|-X---- 0 --X-|-- 0 ----X-- 0
1 --|-|-|-X-- 0 ----X-- 0 ----X-- 0
1 --X-|-|-|-- 1 --X---- 1 --X---- 0
0 ----X-|-|-- 0 --|-X-- 0 --X---- 1
0 ------X-|-- 1 --X-|-- 1 ----X-- 1
0 --------X-- 1 ----X-- 1 ----X-- 1

• 合并网络：将两个有序序列排序。修改双调排序网络的第一个清洁器即可，$O(\log n)$。

0 --X--------X----X---- 0
0 --|-X------|-X--X---- 0
1 --|-|-X----X-|----X-- 0
1 --|-|-|-X----X----X-- 0
0 --|-|-|-X--X----X---- 0
0 --|-|-X----|-X--X---- 1
0 --|-X------X-|----X-- 1
1 --X----------X----X-- 1

• 最后用归并排序的方法连接合并网络，$O(\log^2 n)$。

1 --X---- 0 --X----X---- 0 --X--------X----X---- 0
0 --X---- 1 --|-X--X---- 0 --|-X------|-X--X---- 0
1 ----X-- 0 --|-X----X-- 1 --|-|-X----X-|----X-- 0
0 ----X-- 1 --X------X-- 1 --|-|-|-X----X----X-- 0
0 --X---- 0 --X----X---- 0 --|-|-|-X--X----X---- 0
1 --X---- 1 --|-X--X---- 0 --|-|-X----|-X--X---- 1
0 ----X-- 0 --|-X----X-- 0 --|-X------X-|----X-- 1
0 ----X-- 0 --X------X-- 1 --X----------X----X-- 1

后记：排序网络说明，只要用合理的方法集成电路，排序的复杂度是可以做到 $O(\log^2 n)$ 的。不知道是不是排序复杂度的下界。而且这和交换次数 $O(n\log n)$ 的理论下界并不矛盾，因为 $O(n\log n)$ 没有考虑并行操作。

参考：IOI中国国家候选队论文 - 2002 符文杰