バッチャー奇偶マージソート
バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は Ken Batche(en:Ken Batcher) によって考案された、要素数nに対して、大きさ O(n (log n)) かつ深さ O((log n)) のソーティングネットワークである。これは漸近的に最適(en:asymptotically optimal algorithm)ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、Batcheの方法のほうが (AKSネットワークよりも) 優れている。」と言った。 the second GPU Gems bookの中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。