バイトニックソート
バイトニックマージソート(英語: Bitonic mergesort)または単にバイトニックソート(英語: Bitonic sort)とは、ソートの並列アルゴリズムの1つ。ソーティングネットワークの構築法としても知られている。
このアルゴリズムはケン・バッチャー(英語: Ken Batcher)によって考案されたもので、このソーティングネットワークの計算量は n {\displaystyle n} 個の要素に対して、サイズ(コンパレータ数=比較演算の回数)は O ( n log 2  ( n ) ) {\displaystyle O(n\log ^{2}(n))} 、段数(並列実行不可能な数)は O ( log 2  ( n ) ) {\displaystyle O(\log ^{2}(n))} となる。各段での比較演算(n/2回)は独立して実行できるため、並列化による高速化が容易である。
バイトニックソートでは、バイトニック列(英語: bitonic sequence)を生成しながら並べ替えを実行する。このバイトニック列は、単調非増加の後に単調非減少となるかその逆である列のことである。つまり、k個目までは昇順でそれ以降は降順(つまり、 0 ≤ k < n {\displaystyle 0\leq k<n} に対して x 0 ≤ ⋯ ≤ x k ≥ ⋯ ≥ x n − 1 {\displaystyle x_{0}\leq \cdots \leq x_{k}\geq \cdots \geq x_{n-1}} )もしくはその循環シフトされたものである。