ソーティングネットワーク
この入力列にfを適用(つまりx,yをf(x),f(y)に変換)し、対象のネットワークに入力すれば出力はmin(f(x), f(y)) = f(min(x, y)),max(f(x), f(y)) = f(max(x, y))を満たす。これは、元の入力列と同じ順序を守っていることに他ならない。これを数学的帰納法によって拡張し、n本のワイヤについて証明できる。
このようにfによって出力の順番は保たれることを考えれば、今考えているネットワークがこの入力列を正しくソートできない時、同様に変換後の入力列f(a1), ..., f(an)も正しくソートできないはずである。 この対偶によって、単調増加関数fについてf(a1), ..., f(an)が正しくソートできることを示すことができれば、元の入力列も正しくソートできることになる。 ここで、入力列a1, ..., anについて、列中のいずれかの値より小さくなる値、つまりあるjに対してai < ajとなるようなiを選び、fを
f ( x ) = { 1 if x > a i 0 otherwise. {\displaystyle f(x)={\begin{cases}1\ &{\mbox{if }}x>a_{i}\\0\ &{\mbox{otherwise.}}\end{cases}}}
とする。これは単調増加関数であるため上記の条件を満たし、かつ、変換後の入力列は0と1のみからなる。
以上より、0と1のみからなる数列が対象のネットワークで正しくソートできていることが示されていれば、任意の入力値に対しても正しくソートできることの証明となる。
0-1原理は、W. G. Bouriciusによって1954年に証明されたBouriciusの定理の特別な場合である。
挿入ソートのネットワークの段数は O(n) となり、実用的ではない。バッチャー奇偶マージソート(en:Batcher odd-even mergesort)やバイトニックソート(en:bitonic sort)、シェルソートといった、段数O((log n)) (すなわち、全体のサイズは O(n (log n)) )の単純なネットワークが存在し、実際によく用いられている。