Bitonic sorter

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

O

(

n

(

log

⁡

n

)

2

)

{\displaystyle {\mathcal {O}}(n(\log n)^{2})}

comparators and have a delay of

O

(

(

log

⁡

n

)

2

)

{\displaystyle {\mathcal {O}}((\log n)^{2})}

, 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 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

m

{\displaystyle m}

for which

x

0

≤

⋯

≤

x

m

≥

⋯

≥

x

n

−

1

.

{\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

n

{\displaystyle n}

is a perfect power of two.