バイトニックソート

**バイトニックマージソート**（）または単に**バイトニックソート**（）とは、ソートの並列アルゴリズムの１つ。ソーティングネットワークの構築法としても知られている。

このアルゴリズムはによって考案されたもので、このソーティングネットワークの計算量はn個の要素に対して、サイズ（コンパレータ数＝比較演算の回数）はO(n\log^2(n))、段数（並列実行不可能な数）はO(\log^2(n))となる。各段での比較演算（n/2回）は独立して実行できるため、並列化による高速化が容易である。

バイトニックソートでは、**バイトニック列**（）を生成しながら並べ替えを実行する。このバイトニック列は、単調非増加の後に単調非減少となるかその逆である列のことである。つまり、k個目までは昇順でそれ以降は降順（つまり、0 \leq k に対してx_0 \leq \cdots \leq x_k \geq \cdots \geq x_{n-1}）もしくはその循環シフトされたものである。

## アルゴリズムの動作原理

バイトニックソートは比較と統合の2つの操作からなり、それぞれ入力列と出力列を持つ。

比較の操作では、入力列の上半分が下半分と決められた同じ方向に比較される。
もし入力がバイトニック列であれば、出力は上半分と下半分がそれぞれバイトニック列になり、かつ、上半分の各要素の値は下半分のどの点の値より小さいか等しくなるもしくはその逆のはずである。この法則は、0と1のみからなるバイトニック列には0,1または1,0の列が2つ以上ないことを考えれば、0-1原理を用いて確認することができる。

統合の操作では、入力列に対して、比較の操作を上半分と下半分に分割して適用し、さらにそれぞれを上下分割することを繰り返すとなっている。
入力列がバイトニック列であれば、出力列は比較の方向に従って全体の並べ替えが完了する。なぜなら、先述の通り比較操作では出力の上半分が下半分より大きい（または小さい）ようになるため、上半分と下半分をさらに比較の操作を適用することで、各四分割された列がそれぞれ順に並ぶ。これを最小単位まで繰り返すことで、全体の並べ替えが達成されるのである。

ソーティングネットワーク全体は、この統合の操作によって構成されている。並べ替えの方向を逆にした統合の操作を交互に並べることで、それらの出力を結合した倍の長さの列は、バイトニック列となる。最初は2要素の入力（自明なバイトニック列）から開始され、全体が1つに統合されるまで繰り返し適用される。

### 別の表現方法

先述の表現では、比較の操作において方向を変化させるような方法で説明した。
しかし、比較の方向を同じに揃える表現も可能である。

そのために、入力の下半分だけを上下反転させてから通常の比較操作をする新しい操作を定義する。
そして、先述の方法から、各統合の操作の最初の比較操作を、この操作に置き換える。

こうすると、並べ替えの方向は全て同じにすることができるため、この表現方法が、バイトニックソートの最も普遍的な表現方法となる。

## 実装例
以下に、再帰呼び出しを用いたPythonを用いたバイトニックソートの実装例を示す。入力は、論理値*up*と2べき乗個の配列*x*であり、出力は、*up*が真であれば昇順、でなければ降順となる。

```python
def bitonic_sort(up: bool, x: Sequence[int]) -> List[int]:
    """バイトニックソート

    引数:
      up: 真であれば昇順、偽であれば降順
      x: 整数列

    Returns:
      upに従って並べ替えられた整数列
    """
    if len(x) <= 1:
        return x
    else: 
        first = bitonic_sort(True, x[:len(x) // 2])
        second = bitonic_sort(False, x[len(x) // 2:])
        return bitonic_merge(up, first + second)

def bitonic_merge(up: bool, x) -> List[int]: 
    # 入力xがバイトニック列であれば、並べ替えられて出力される
    if len(x) == 1:
        return x
    else:
        bitonic_compare(up, x)
        first = bitonic_merge(up, x[:len(x) // 2])
        second = bitonic_merge(up, x[len(x) // 2:])
        return first + second

def bitonic_compare(up: bool, x) -> None:
    dist = len(x) // 2
    for i in range(dist):
        if (x[i] > x[i + dist]) == up:
            x[i], x[i + dist] = x[i + dist], x[i]  # 交換
```



```pycon
>>> bitonic_sort(True, [10, 30, 11, 20, 4, 330, 21, 110])
[4, 10, 11, 20, 21, 30, 110, 330]
>>> bitonic_sort(False, [10, 30, 11, 20, 4, 330, 21, 110])
[330, 110, 30, 21, 20, 11, 10, 4]
```


再帰呼び出しを用いない例（Javaによる）は以下のようになる。


```java
public class BitonicSort {
    static void kernel(int[] a, final int p, final int q) {
        final int d = 1 << (p-q);

        for (int i = 0; i < a.length; i++) {
            boolean up = ((i >> p) & 2) == 0;

            if ((i & d) == 0 && (a[i] > a[i | d]) == up) {
                int t = a[i];
                a[i] = a[i | d];
                a[i | d] = t;
            }
        }
    }

    static void bitonicSort(final int logn, int[] a) {
        assert a.length == 1 << logn;

        for (int i = 0; i < logn; i++) {
            for(int j = 0; j <= i; j++) {
                kernel(a, i, j);
            }
        }
    }

    public static void main(String[] args) {
        final int logn = 5, n = 1 << logn;

        int[] a0 = new int[n];
        for (int i = 0; i < n; i++) {
            a0[i] = (int)(Math.random() * 1000);
        }

        for (int k = 0; k < a0.length; k++) {
            System.out.print(a0[k] + " ");
        }
        System.out.println();

        bitonicSort(logn, a0);

        for (int k = 0; k < a0.length; k++) {
            System.out.print(a0[k] + " ");
        }
        System.out.println();
    }
}
```


## 脚注


## 関連項目
* バッチャー奇偶マージソート

## 外部リンク
*A discussion of this algorithm
*Reference code at NIST
*Tutorial with animated pictures and working code