バッチャー奇偶マージソート

 バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は Ken Batche() によって考案された、要素数nに対して、大きさ O("n" (log "n")2) かつ深さ O((log "n")2) のソーティングネットワークである。これは漸近的に最適（）ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、Batcheの方法のほうが (AKSネットワークよりも) 優れている。」と言った。
the second GPU Gems bookの中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。
Pythonによる実装例.
入力として、2の累乗の長さを持ったリストを取り、ソート済みリストを返す。
def compare_and_swap(x, a, b):
 if x[a] > x[b]:
 x[a], x[b] = x[b], x[a]
def oddeven_merge(x, lo, hi, r):
 step = r * 2
 if step < hi - lo:
 oddeven_merge(x, lo, hi, step)
 oddeven_merge(x, lo + r, hi, step)
 for i in range(lo + r, hi - r, step):
 compare_and_swap(x, i, i + r)
 else:
 compare_and_swap(x, lo, lo + r)
def oddeven_merge_sort_range(x, lo, hi):
 """ 区間lo と hiのソートを行う。
 注意: 端点 (lo と hi) は含むものとする。
 if (hi - lo) >= 1:
 # ひとつ以上の要素があった場合、入力を
 # 長さの半分で前後に分割し、
 # その後それぞれをマージソートする。
 mid = lo + ((hi - lo) / 2)
 oddeven_merge_sort_range(x, lo, mid)
 oddeven_merge_sort_range(x, mid + 1, hi)
 oddeven_merge(x, lo, hi, 1)
def oddeven_merge_sort(x):
 oddeven_merge_sort_range(x, 0, len(x)-1)
»> data = [2, 4, 3, 5, 6, 1, 7, 8]
»> oddeven_merge_sort(data)
»> data
[1, 2, 3, 4, 5, 6, 7, 8]