Bitonic-Sort - tattyu's blog

t-pot氏のところで見たのがずっと気になっていたので、調べてみた。

なんだJavaのソースあるじゃねぇか。
いっちょqsortと比較してみようということで比較したら、3倍くらい遅かった。
せっかくだし再帰呼び出しを展開しようと思ったが、その前にちゃんとソートできてんのかと。

奇数個の要素の時にうまくいかない気がしていたのでチェックしたら案の定駄目だった。
アルゴリズム的にも、2のn乗じゃないとうまくいかない感じだし。

じゃぁバイトニックってなんじゃいと思って調べた。
2のn乗のこと？（そういえば2のn乗の良い呼び方って無いの？）

今はこういう便利なサイトがあるんで調べると
http://homepage2.nifty.com/PAF00305/math/writing.html

2のn乗は
2〔raised〕to the n-th〔power〕
らしい。

でもさっきのソートの条件から想像するにやっぱり2のn乗のことなのかな。
そもそも元のサイトが英語じゃないので良く分かりません。

とりあえず汎用的な関数にしようと思うと2のn乗しばりを解決しないと駄目なので微妙ですね。
一応要素が2のn乗じゃないときは無理やり2のn乗にして、余ったスペースは最大値かなんかでフィルしておけばソート自体はうまくいくのだけれどやっぱし使いどころがむづかしいなと思った。