バッチャー奇偶マージソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/07/29 02:48 UTC 版)
バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は Ken Batche(en:Ken Batcher) によって考案された、要素数nに対して、大きさ O(n (log n)2) かつ深さ O((log n)2) のソーティングネットワークである。これは漸近的に最適（en:asymptotically optimal algorithm）ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、Batcheの方法のほうが (AKSネットワークよりも) 優れている。」と言った。[1] the second GPU Gems book[2]の中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。
| ||||||||||||||||||||||
- ^ 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.
- ^ https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html
[続きの解説]
「バッチャー奇偶マージソート」の続きの解説一覧
- 1 バッチャー奇偶マージソートとは
- 2 バッチャー奇偶マージソートの概要
- バッチャー奇偶マージソートのページへのリンク
