Bitonic sorter

Bitonic sorter

Bitonic sorting network (bitonic merge sort) with 4 inputs with an example sequence that is being sorted.
Class	Sorting algorithm
Data structure	Array
Worst-case performance	${\displaystyle {\mathcal {O}}((\log n)^{2})}$ parallel time
Best-case performance	${\displaystyle {\mathcal {O}}((\log n)^{2})}$ parallel time
Average performance	${\displaystyle {\mathcal {O}}((\log n)^{2})}$ parallel time
Worst-case space complexity	${\displaystyle {\mathcal {O}}(n(\log n)^{2})}$ non-parallel time
Optimal	No

Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of ${\displaystyle {\mathcal {O}}(n(\log n)^{2})}$ comparators and have a delay of ${\displaystyle {\mathcal {O}}((\log n)^{2})}$, where ${\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 lockstep, such as a typical GPU.

A sorted sequence is a monotone sequence---that is, a sequence which is either non-decreasing or non-increasing. A sequence is bitonic when it consists of a non-decreasing sequence followed by a non-increasing sequence, i.e. when there exists an index ${\displaystyle m}$ for which ${\displaystyle x_{0}\leq \cdots \leq x_{m}\geq \cdots \geq x_{n-1}.}$

A bitonic sorter can only sort inputs that are bitonic. Bitonic sorters can be used to build a bitonic sort network that can sort arbitrary sequences by using the bitonic sorter with a sort-by-merge scheme, in which partial solutions are merged using bigger sorters.

The following sections present the algorithm in its original formulation, which requires an input sequence whose length ${\displaystyle n}$ is a perfect powers of two. We will therefore let ${\displaystyle k=\log _{2}(n)}$ be the integer for which ${\displaystyle n=2^{k}}$, meaning that the bitonic sorters may be enumerated in order of increasing size by considering the successive values ${\displaystyle k=1,2,3,\ldots }$.