Bitonic sorter

Bitonic mergesort is a <a href="/facts/Parallel_algorithm/nUPzEF4C">parallel algorithm</a> for sorting. It is also used as a construction method for building a <a href="/facts/Sorting_network/ceMfQqSh">sorting network</a>. The algorithm was devised by <a href="/facts/Ken_Batcher/NBNAtFmM">Ken Batcher</a>. The resulting sorting networks consist of 
 
 
 
 O
 (
 n
 
 log
 
 2
 
 
 ⁡
 (
 n
 )
 )
 
 
 {\displaystyle O(n\log ^{2}(n))}
 
 comparators and have a delay of 
 
 
 
 O
 (
 
 log
 
 2
 
 
 ⁡
 (
 n
 )
 )
 
 
 {\displaystyle O(\log ^{2}(n))}
 
, where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of items to be sorted. This makes it a popular choice for sorting large numbers of elements on an architecture which itself contains a large number of parallel execution units running in <a href="/facts/Lockstep_(computing)/KbfWl3g4">lockstep</a>, such as a typical <a href="/facts/Graphics_processing_unit/PTK1RQVp">GPU</a>.
A sorted sequence is a monotonically non-decreasing (or non-increasing) sequence. A bitonic sequence is a sequence with 
 
 
 
 
 x
 
 0
 
 
 ≤
 ⋯
 ≤
 
 x
 
 k
 
 
 ≥
 ⋯
 ≥
 
 x
 
 n
 −
 1
 
 
 
 
 {\displaystyle x_{0}\leq \cdots \leq x_{k}\geq \cdots \geq x_{n-1}}
 
 for some 
 
 
 
 k
 ,
 0
 ≤
 k
 <
 n
 
 
 {\displaystyle k,0\leq k<n}
 
, or a circular shift of such a sequence.

Bitonic sorter open-in-new

Bitonic sorter