バイトニックソートを理解する（16要素のデータを例に）

はじめに

実践Rust入門を読み進めています。3章ではバイトニックソート(Bitonic sort)を例にRustのクイックツアーをするのですが、私は本書でバイトニックソートが初見のため理解に時間がかかりました。ようやく理解できたので、ブログに備忘録しておきます。
en.wikipedia.org

バイトニックソートの特徴

• 計算量がデータの要素数で決まり、常にO(nlogn)。
• データの要素数が2のべき乗でないといけない。全ての要素数に対応するにはダミーデータ追加などの対応が必要。
• アルゴリズムはソーティングネットワークのモデルで表され、容易に並列化できる*1。

バイトニックソートのアルゴリズム

1. 「昇順＋降順のバイトニック列」にする。
2. 2^n･･･2^0間を昇順（降順）で比較する。

バイトニックソート - 高速化プログラミング

バイトニック列とは前半と後半が逆の順序で並んでいるデータ列のこと。

バイトニックソートの実例

16要素を手動ソートしつつ、Rustのデバッガ環境で逐次ソートの状況を確認することでようやく理解できました。その逐次処理をまとめたのが下記の図になります。
ソートするデータ：[10,30,11,20,4,330,21,110,12,31,15,22,41,331,220,111]

前半８要素を昇順にソートするステップ

同じ色でハッチングした要素がスワップした箇所になります。
midpointによって比較する要素が決定します。

後半8要素を降順にソートし全16要素を昇順ソートするステップ

理解が難しかった点

書籍やWebページを読んでも最初は全く理解できませんでした。アルゴリズムの説明文からステップ1が完了して、ステップ2を行うように思うのですが、そうではないことを理解する必要がありました。
wikipediaの実装例からわかるのですが、再帰的に関数コールして、最初のスワップ処理は隣の要素との比較になります。そこから2^n乗離れた要素と比較していったり、また2^0乗離れた（つまり、隣）要素と比較したりを繰り返します。そのいったりきたりがイメージしにくかったです。

ポイント

• 最初は配列を1/2ずつしていき、隣の要素と比較する。
• 1/2していく時に、前半は昇順、後半は降順にソートするように設定する。
• 結合していくときは、親がコールした順序に従ってソートする。

おわりに

Rustに入門しようとしたら、ソートアルゴリズムの知識不足で１回休みという感じになりました。それでもデバッガ使いつつ、理解するところまで到達できたので良かったです。デバッガが非常に理解の助けになりました。

*1:この部分はまだ理解不足