图论：比较网络

比较网络由电线和比较器组成。比较器是具有两个输入x和y以及两个输出x’和y’的设备, 其中

x’=最小值（x, y）y’=最大值（x, y）

在“比较网络”中, 输入出现在左侧, 输出出现在右侧, 最小的输入值出现在顶部的输出中, 最大的输入值出现在底部的输出。每个比较器以O（1）时间运行。换句话说, 我们认为输入值x和y的出现与输出值x’和y’的产生之间的时间是恒定的。

电线从一个地方传送一个值。一个比较网络包含n条输入线a1, a2, …. an, 要通过其排序的收益进入网络, n条输出线b1, b2, … bn产生结果由网络计算。

比较网络是一组通过电线互连的比较器。比较器的运行时间可以定义深度。

线的深度：比较网络的输入线的深度为0。现在, 如果比较器的两条输入线的深度为dx和dy’, 则其输出线的深度为max（dx, dy）+ 1。

排序网络是一个比较网络, 对于该比较网络, 每个输入序列的输出序列都将单调递增（即b1≤b2≤…. bn）。

图：基于插入排序的排序网络