ソーティングネットワーク
AKSネットワーク(発見者のAjtai(en:Miklós Ajtai)、Komlós(en:János Komlós (mathematician))、Szemerédi(en:Endre Szemerédi)にちなむ)というソーティングネットワークは、 n 個の入力に対して段数 O(log n) ・サイズ O(n log n) となる。これは漸近的に最適なアルゴリズム(英語: asymptotically optimal algorithm)である。また、このAKSネットワークを簡潔にしたものが後にPaterson(en:Mike Paterson)によって発表されている。AKSネットワークは重要な発見ではあるが、Big-O 記法に隠された巨大な定数があり、実用に供されることはほとんどない。この理由のひとつとしては、エキスパンダーグラフ(en:expander graph)の構成が挙げられる。小さな c に対してサイズ cn log n のソーティングネットワークを見つけるのは、依然として未解決問題のままである。
1個から8個までの入力に対しては最適なソーティングネットワークが知られており、それぞれ 0, 1, 3, 5, 9, 12, 16, 19 個のコンパレータを持つ (Knuth, 1997)。10個までの入力に対する最小の段数も知られており、それぞれ 0, 1, 3, 3, 5, 5, 6, 6, 7, 7 である。
ソーティングネットワーク(英: sorting network)とは、ワイヤとコンパレータからなる、数列をソートするネットワーク(抽象的な数理モデル)である。一つのコンパレータが二つのワイヤを繋ぎ、小さい方の値を一方に、大きい方の値を他方に出力する。これによって値のソートが行われる。比較ソートアルゴリズムとソーティングネットワークの主な違いは、比較の順序が、それまでの比較の結果によらずあらかじめ決まっていることである。このため、アルゴリズムを並列に実行することが容易である。モデルは単純だが、ソーティングネットワークの理論は非常に深く、複雑である。
挿入ソートやバブルソートのネットワークのように、簡単に正当性を示せるソーティングネットワークも存在するが、正当性が常に簡単に示せるとは限らない。n 本のワイヤからなるネットワークに対し、 n ! {\displaystyle n!} 通り全ての場合を試すには、(大きなネットワークでは特に)時間がかかる。しかし、いわゆる0-1原理(zero-one principle)によれば、実際には遥かに少ない試行で十分である。
0-1原理とは、「あるネットワークが0と1からなる 2 n {\displaystyle 2^{n}} 通りの数列全てをソートすることが出来れば、それは正当なソーティングネットワークである」というものである。0-1原理によって、ソーティングネットワークの正当性を確かめるのに必要な試行の回数は大幅に減る。0-1原理は、様々なソーティングネットワークを構成するためにも有用である。
この原理の証明の大枠は次の通り。
初めに、今、正当性を証明したいn本のワイヤからなるあるネットワークが、n個の数列a1, ..., anを入力された時、b1, ..., bnと出力すると考える。 この時、この入力列に対して単調増加関数fを適用し、入力列をf(a1), ..., f(an)に変換しても、このネットワークの出力はf(b1), ..., f(bn)の順となるはずである。 これを示すには、まずx,yの2つの値が入力されるネットワーク(2本のワイヤと1つのコンパレータからのみ構成されている)について考える。