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

バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は、によって考案された、要素数nに対して、大きさ O(n (log n)2) かつ深さ O((log n)2) のソーティングネットワークである。これは漸近的に最適（:en:asymptotically optimal algorithm）ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、バッチャーの方法のほうが (AKSネットワークよりも) 優れている」と述べたD.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.。NVIDIAの技術者であるの編によるGPU Gems 2https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.htmlの中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。

 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]


 参考文献 

 外部リンク 

Odd–even mergesort at fh-flensburg.de

Category:ソート
Category:エポニム