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

バッチャー奇偶マージソート（Batcher's odd-even mergesort）は、ケン・バッチャーによって開発された、並列ソートアルゴリズムの一種です。このアルゴリズムは、ソートネットワークとして実装されることが特徴で、特にハードウェアでの並列処理に適しています。要素数nのデータに対して、その規模はO(n(log n)^2)、深さはO((log n)^2)で表現されます。

アルゴリズムの特徴

バッチャー奇偶マージソートは、名前の通り、奇数番目と偶数番目の要素を比較・交換する操作を繰り返すことで、データをソートします。この比較・交換の操作は、並列に実行できるため、ハードウェアによる高速な処理が可能です。アルゴリズムは、マージソートの考え方をベースにしており、より小さなソートされた部分列をマージすることで、最終的なソート結果を得ます。

計算量について

バッチャー奇偶マージソートの計算量は、要素数nに対して、サイズがO(n(log n)^2)、深さがO((log n)^2)です。漸近的に最適なアルゴリズムではありませんが、実用的な範囲においては、その効率性から広く利用されています。特に、GPUなどの並列処理ハードウェアにおいては、その特性を活かして高速なソート処理を実現できます。

実用例

特にGPU Gems 2で紹介されたことで知られ、グラフィックスプロセッシングユニット（GPU）を活用した効率的なソートの実装方法として注目されました。GPUのような並列処理が得意なハードウェアにおいて、バッチャー奇偶マージソートは高いパフォーマンスを発揮します。

ドナルド・クヌースの言及

ドナルド・クヌースは、AKSネットワークという漸近的に最適なソートアルゴリズムに対し、「nが地球上の全てのコンピュータのメモリに収まらないほど巨大でなければ、バッチャーの方法が優れている」と述べています。この発言からも、バッチャー奇偶マージソートの実用的な価値が理解できます。

Pythonでの実装例

python
def odd_even_merge(lo, hi, r):
step = 1 << r
if step < hi - lo:
odd_even_merge(lo, hi, r - 1)
odd_even_merge(lo + step, hi, r - 1)
for i in range(lo + step, hi, 2 step):
compare_and_swap(i, i - step)


def compare_and_swap(i, j):
if arr[i] < arr[j]:
arr[i], arr[j] = arr[j], arr[i]

def batcher_sort(list):
global arr
arr = list
n = len(arr)
r = (n - 1).bit_length()
odd_even_merge(0, n, r)
return arr


上記のコードは、2の累乗の長さを持つリストをソートするPythonでの実装例です。

まとめ

バッチャー奇偶マージソートは、並列処理に適したソートアルゴリズムであり、特にGPUなどのハードウェアによる高速なソート処理に貢献しています。その実装の容易さや、実用的な範囲における高いパフォーマンスから、広く利用されています。

参考文献

GPU Gems 2

外部リンク

* Odd–even mergesort at fh-flensburg.de

もう一度検索