ビトニックソート入門
バイトニックソート
バイトニックソートは、並列計算をサポートするソートアルゴリズムです。単純な比較とスワップのみを使用するため、GPUやNPUなどの多数の並列実行ユニットを備えたアーキテクチャで多数の要素をソートするのに適しています。
ソート処理は一般的に2つのステップで構成されます。最初のステップでは、配列を上から下に向かってバイトニックシーケンスに分割します。2番目のステップでは、これらのシーケンスを下から上に向かって単一の単調シーケンスにマージします。以下のセクションでは、バイトニックシーケンスとは何か、そして分割とマージのプロセスについて説明します。
バイトニックシーケンス
バイトニックシーケンスとは、最初は単調増加し、次に単調減少する（または最初は単調減少し、次に単調増加する）数値のシーケンスです。例えば、次の3つのデータセットはすべてバイトニックシーケンスと見なすことができます。
- 増分と減分のデータサイズが同じ場合:
[1, 4, 5, 6, 3, 2]: ↗↘ (1, 4, 5) 増加、(6, 3, 2) 減少[8, 2, 1, 3]: ↘↗↘↗ (8, 2) 減少、(1, 3) 増加 - 増分と減分のデータサイズが異なる場合:
[1, 2, 4, 7, 6, 3]: ↗↘ (1, 2, 4, 7) 増加、(6, 3) 減少 - 増分と減分が 0 の場合:
[1, 2, 3]: ↗(1, 2, 3) 増加、() 減少[6]: ↗(6) 増加、() 減少 [または ↘() 増加、(6) 減少]
上記の3つのビットーンシーケンスの集合から、ビットーンシーケンスの定義をまとめることができます（増加してから減少するシーケンスを例に挙げます）。シーケンス nums に対して、インデックス が存在し、インデックスが 以下のすべての要素 nums[:i] に対してシーケンスは単調増加し、インデックスが 以上のすべての要素 nums[i:] に対してシーケンスは単調減少します。
比較とスワップ
比較とスワップはビットーンソート処理の不可欠な部分であり、処理全体を通して複数の操作を必要とします。比較対象となる2つの数値 nums[i] と nums[j] について、増加シーケンスと減少シーケンスの処理ロジックは以下のように定義されます。
nums[i]とnums[j]は増加シーケンスです。
nums[i] > nums[j]->swap(nums[i], nums[j])nums[i] <= nums[j]->do nothing
nums[i]とnums[j]は減少シーケンスです。
nums[i] < nums[j]->swap(nums[i], nums[j])nums[i] >= nums[j]->do nothing
ビットーンシーケンスの連続の作成
ビットーンシーケンスを使えば、任意のデータセットをビットーンシーケンスの組み合わせに分割できます。説明を簡単にするため、ここでは奇数の場合については考慮しません。
[3, 6, 5, 7, 4, 1, 8, 2] を例に挙げると、まず半分に分割します。
[3, 6, 5, 7]、[4, 1, 8, 2]。次に、各部分をさらに半分に分割します。
[3, 6]、[5, 7]、[4, 1]、[8, 2]。次に、各部分をさらに半分に分割します。
[3]、[6]、[5]、[7]、[4]、[1]、[8]、[2]。
バイトニックシーケンスの3番目の例（増加データと減少データは0）に基づくと、このデータセットは増加シーケンスと減少シーケンスの組み合わせの連続として見ることができます。
バイトニックマージ
バイトニックマージは、バイトニックソートの2番目のステップです。その機能は、バイトニックシーケンスのグループをモノトニックシーケンスの新しいグループに結合し、最終的にモノトニックシーケンス（これもバイトニックシーケンスです）を形成することです。マージされた各シーケンスはバイトニックシーケンスでなければならないこと、そして1回のマージ後の結果は厳密にモノトニックでなければならないことに注意することが重要です。 [3, 6, 5, 7, 4, 1, 8, 2] を例に挙げると、これはすでに 8 つの単調なシーケンスグループに分割されているため、…
ステップ 1: シーケンスのペアを結合して 4 つのビットトーンシーケンスを作成します。結合すると 4 つのモノトーンシーケンス、つまり 8 つの 1 が 4 つの 2 に結合します。
ステップ 2: 4 つのモノトーンシーケンスを結合して 2 つのビットトーンシーケンスを作成します。結合すると 2 つのモノトーンシーケンス、つまり 4 つの 2 が 2 つの 4 に結合します。
ステップ 3: 2 つのモノトーンシーケンスを結合して 1 つのビットトーンシーケンスを作成します。結合すると 1 つのモノトーンシーケンス、つまり 2 つの 4 が 1 つの 8 に結合します。
結合規則は、n 回目の結合では結果が昇順 (ascend) に並べられ、(n+1) 回目の結合では結果が降順 (descend) に並べられるというものです。ビットトーン列を半分に分割し、各桁を比較し、「比較と交換」で説明した規則に従って昇順（または降順）で比較と交換を行います。次に、交換したデータの半分をさらに半分に分割し、昇順（または降順）で比較と交換を行います。残りの半分についても、比較可能な最小単位に達するまでこの処理を繰り返します。最終的な組み合わせが結果です。
比較可能な最小単位：これは、2つの数値のみを比較する場合を指します。1つの数値に分割する際に、それ以上比較する必要がないためです。
1 と 2 をマージ
入力データについて、左から右へのペアの組み合わせは、[3] [6]、[5] [7]、[4] [1]、[8] [2] となります。組み合わせ規則によると、「n 回目のマージでは結果は昇順（ascend）に、n+1 回目のマージでは降順（descend）に並べられます」。
1 回目と 3 回目のマージは昇順のままです。
比較とスワップの規則によると、昇順で、a > b の場合は a と b を入れ替え、a <= b の場合は変更しません。したがって、3 と 6 を比較する場合は変更しません。4 と 1 を比較する場合はスワップが行われます。これはすでに最小の比較単位であるため、さらに分割する必要はありません。 
2番目と4番目のマージは降順のままです。
比較とスワップの規則に従い、降順で、a < b の場合は a, b を交換し、a >= b の場合は変更しません。したがって、8と2を比較する場合は変更されません。5と7を比較する場合はスワップが発生します。これはすでに最小の比較単位であるため、さらに分割する必要はありません。 
マージ結果
マージ後の結果は [3, 6] [7, 5] [1, 4] [8, 2] です。
マージ 2 から 4
入力データ [3, 6]、[7, 5]、[1, 4]、[8, 2] を、次の組み合わせ規則に従って、左から右へペアごとに結合します。「n 回目のマージでは結果は昇順 (ascend) になり、(n+1) 回目のマージでは結果は降順 (descend) になります。」
最初のマージは昇順を維持
昇順のシーケンスでは、3 と 7 は変更されず、6 と 5 が入れ替わり、[3, 5, 7, 6] になります。現在の結果は最小の比較単位ではないため、2 つの SubMerge が実行され、シーケンスが半分に分割されてからマージが続行されます。SubMerge では、3 と 5 が比較されて変更されず、7 と 6 が入れ替わります。最終結果は [3, 5, 6, 7] です。
2回目のマージ、降順を維持
降順のシーケンスでは、4と2は変化せず、1と8が入れ替わり、[8, 4, 1, 2] になります。現在の結果は最小の比較単位ではないため、2回のサブマージが実行され、シーケンスが半分に分割されてからマージが続行されます。サブマージでは、8と4が比較され、変化しませんが、1と2が入れ替わります。最終結果は [8, 4, 2, 1] です。
マージ結果
マージ結果は [3, 5, 6, 7] [8, 4, 2, 1] になります。
4 と 8 のマージ
ビットニックシーケンス [3, 5, 6, 7] [8, 4, 2, 1] の各要素を比較します。マージは 1 つしか残っていないため、このマージでは昇順が維持されます。
昇順マージ
増加交換規則に従い、最初のマージでは 3 と 8 は変更されませんが、5 と 4、6 と 2、7 と 1 を交換する必要があります。現在の結果が比較の最小単位でない場合は、SubMerge 操作を 2 回実行します。[3, 4, 2, 1] の場合、3 と 2、および 4 と 1 を入れ替える必要があります。[8, 5, 6, 7] の場合、8 と 6 を入れ替える必要があります。SubMerge 操作後も結果が比較の最小単位でない場合は、各 SubMerge に対してさらに 2 回 SubMerge 操作を実行し、2 と 1、6 と 5、8 と 7 を入れ替えます。
マージ後の結果
マージ後の結果は [1, 2, 3, 4, 5, 6, 7, 8] になります。
したがって、3回のMerge操作と複数のSubMerge操作を実行することで、単調順序のシーケンスが得られます。### 利点と欠点
利点：並列処理をサポート、高いソート効率（計算時間が少ない）、タイルベースの計算をサポート。
欠点：非並列シナリオでは実行速度が低下する、大量の入力データが必要（n = 2^k）、アルゴリズムの実装が比較的複雑。