読者です 読者をやめる 読者になる 読者になる

c++11constexprでコンパイル時バイトニックソートを大雑把に実装した

C++

ネタではなく非常に強力であり実用的なソートである
//コード
bitonic_sort.hpp
//実行結果
[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

ちなみに一部コードは
C++11 constexprでマージソート - ここは匣
から借りてきた




バイトニックソートとはマージソートの亜種であり、マージソート以上に並列実行に特化したソートアルゴリズムである
ギミックが美しい。とても美しい。ミニマルを感じる

おおまかな動きはここを見てほしい
バイトニックソート - 高速化プログラミング
詳しいアルゴリズムはここを見てほしい
Bitonic sort

バイトニックソートは再起オーダーO((log N)^2)で実装することができる
これはもはやconstexprするしかない。するべきである
O((log N)^2)というのは実用上十二分に使える数値である。1024要素あっても100*Kだ

O((log N)^2)というオーダーはマージ処理を可能な限り一つの関数で行うことによって実装されている
constexprでも並列実行は有益であるといえる