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. ^[3] The resulting sorting networks consist of ${\displaystyle {\mathcal {O}}(n\log ^{2}(n))}$ comparators and have a delay of ${\displaystyle {\mathcal {O}}(\log ^{2}(n))}$, where ${\displaystyle n}$ is the number of items to be sorted^[1][2]. 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.

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 ^{2}(n))}$ parallel time[1][2]
Best-case performance	${\displaystyle {\mathcal {O}}(\log ^{2}(n))}$ parallel time [1][2]
Average performance	${\displaystyle {\mathcal {O}}(\log ^{2}(n))}$ parallel time[1][2]
Worst-case space complexity	${\displaystyle {\mathcal {O}}(n\log ^{2}(n))}$ non-parallel time[1][2]
Optimal	No

A sorted sequence is a monotonically non-decreasing (or non-increasing) sequence. A sequence is bitonic if it consist of two sequences where exactly one sequence is non-decreasing and the other is non-increasing. Formally this means it exists a ${\displaystyle k,0\leq k<n}$ for which ${\displaystyle x_{0}\leq \cdots \leq x_{k}\geq \cdots \geq x_{n-1}}$^[3].

A bitonic sorter can only sort inputs that are bitonic. Bitonic sorter 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. With the sort by merge scheme part solutions are merged together using bigger sorters. This is further described in the chapter about bitonic sorting networks.

In the following chapters the original algorithm is described, which needs input sequences with ${\displaystyle n=2^{k}}$. Therefore, let ${\displaystyle k=\log _{2}(n)}$ in the following chapters. Therefore the next biggest bitonic sorter from a k-bitonic sorter is a (k+1)-bitonic sorter.

Bitonic Sorter

A normal comparator with two inputs

With a bitonic sorter, only bitonic sequences can be used as inputs. To sort arbitrary input sequences, a bitonic sorting network can be created from bitonic sorters. For bitonic sorting networks, see the next chapter. A bitonic sorter for ${\displaystyle k=1}$ ${\displaystyle (n=2)}$ is trivially just a comparator^[3]. This is illustrated by the given box layout with X and Y being the inputs and H the higher output and L the lower output, respectively.

With the sorter for ${\displaystyle k=1}$, we can recursively create a sorter of higher order. For example, consider the following ${\displaystyle k=1}$ ${\displaystyle (n=2)}$ bitonic sorter^[3].

A ${\displaystyle n=4}$ ${\displaystyle (k=2)}$ bitonic merge sorter

The bitonic sorter consists of two layers: a recombination layer and bitonic sorters of a lower order. The recombination layer recombines the bitonic inputs into two new bitonic sequences that are half as big as the original sequence. In the bitonic sort layer, there are two bitonic sorters of order ${\displaystyle k-1}$ that take the bitonic input of the recombination and sort them again. This can be done recursively for each ${\displaystyle k}$ using an input of each monotonic sequence per comparator. The following illustration shows the connection of the recombination in order for this to work^[3].

test

As you can see, the first half of the input sequence is compared against the last half of the input sequence. Both subsequences are already monotonically decreasing or increasing, respectively. Comparing each element of the (green) subsequence with the element of the other (orange) subsequence at the respective index produces two bitonic subsequences. These two bitonic series (blue and red, respectively) can then be fed into the next lower-order bitonic sorter. This can be done because all elements in the red sequence are guaranteed to be higher than all elements in the blue series^[3].

Proof of the bitonic sorter

Ken Batcher provided some mathematical proof sketch in his paper^[3]. With out loss of generality the bitonic input sequence is assumed to be ${\displaystyle a_{1}\leq a_{2}\leq \dots \leq a_{j-1}\leq a_{j}\geq a_{j+1}\geq \dots \geq a_{2n}}$ with ${\displaystyle 1\leq j\leq 2n}$. With out loss of generality the sequence can be reversed therefore, we can assume ${\displaystyle n\leq j\leq 2n}$.

Case 1: If ${\displaystyle a_{n}\leq a_{2n}}$ then every element of the two subsequences are smaller. In this case ${\displaystyle d_{i}=a_{i}}$ and ${\displaystyle e_{i}=a_{n+i}}$ with ${\displaystyle 1\leq i\leq n}$ and therefore ${\displaystyle d_{i}}$ and ${\displaystyle e_{i}}$ are trivially bitonic.

Case 2: Otherwise there exists a ${\displaystyle k}$ such that the element ${\displaystyle a_{k}}$ of the first sub-sequence is bigger then ${\displaystyle a_{k}}$ of the second sub-sequence while it is the opposite for ${\displaystyle a_{k+1}}$. This means that ${\displaystyle a_{k}\leq a_{k+n}}$ and ${\displaystyle a_{k+1}>a_{k+n+1}}$ are true for a specific ${\displaystyle k}$. Therefore we now know that:

1. For ${\displaystyle 1\leq i\leq k}$ the sequences are ${\displaystyle d_{i}=a_{i}}$ and ${\displaystyle e_{i}=a_{n+i}}$

2. For ${\displaystyle k<i\leq 2n}$ the sequences are defined as the opposite of 1, with ${\displaystyle d_{i}=a_{n+i}}$ and ${\displaystyle e_{i}=a_{i}}$

In the original paper he then claims the following inequalities result from those definitions^[3]:

Following from 1:

• For ${\displaystyle 1\leq i\leq k}$ that ${\displaystyle d_{i}\leq d_{i+1}}$
• For ${\displaystyle j-n\leq i\leq k}$ that ${\displaystyle e_{i}\geq e_{i+1}}$
• For ${\displaystyle 1\leq i\leq j-n}$ that ${\displaystyle e_{i}\leq e_{i+1}}$

Following from 2:

• For ${\displaystyle k<i\leq 2n}$ that ${\displaystyle d_{i}\geq d_{i+1}}$
• For ${\displaystyle k<i\leq 2n}$ that ${\displaystyle e_{i}\leq e_{i+1}}$

From both: ${\displaystyle e_{n}\leq e_{1}}$

From the paper claims follows that the sequences ${\displaystyle d_{i}}$ and ${\displaystyle e_{i}}$ are in fact bitonic^[3].

Bitonic Sorting Networks (Bitonic Merge Sort)

A bitonic sorting network is created by using several bitonic sorters. These bitonic sorters are recursively used to create two monotonic sequences, one decreasing and one increasing, which are then put into the next stage. This creates a bitonic series for the next stage, which can then use this bitonic series as a monotonic series for the next stage. Consider the following example for an ${\displaystyle n=4}$ bitonic sort network ^[3].

test

The bitonic sorting network for ${\displaystyle k=2}$ can be created by using a ${\displaystyle k=2}$ bitonic sorter and two ${\displaystyle k=k_{prev}-1}$ sorters. The two sorters create a decreasingly or increas- ingly sorted sequence in order to create a bitonic input for the bitonic sorter. Bitonic sorting networks of a lower order are mostly used for the two pre-sorters; therefore, a recursive definition of a bitonic sorting network from bitonic sorters can be described. In the above example, the two bitonic sorting networks are ${\displaystyle k=1}$ networks; hence, they are just a comparator ^[3]. The following figure shows the overall scheme.

test

This overall scheme requires the sorter to have an input of sequence that is a power of two. There are, however, possibilities to mitigate this by, for example, using sentinel values.

Complexity

In this chapter we assume that our sorter has ${\displaystyle n=2^{k}}$ input elements. Let therefore ${\displaystyle k=\log _{2}(n)}$ as previously.

Each recursion in a bitonic sorting network adds a sorter of order ${\displaystyle k_{next}=k_{prev}-1}$, which consists of bitonic ${\displaystyle k_{next}}$ sorter and the next recursion. As both sub-sorters can be done in parallel, only one level is added for each level in both sub-sorters. Each bitonic sorter has, therefore, one recombination layer and a lower-order bitonic sorter for its recursion. This results in ${\displaystyle k}$ levels per bitonic sorter. Therefore we can describe this construction's levels as the following sum: ${\displaystyle \sum _{i=1}^{k}i}$.

This sum can be reduced using the Gauss sum formula ${\displaystyle \sum _{i=1}^{k}i={\dfrac {1}{2}}k(k+1)}$

Therefore, the number of levels in which each comparison can be done in parallel is given by ${\displaystyle {\dfrac {1}{2}}k(k+1)}$ ^[3]. Which gives us ${\displaystyle {\mathcal {O}}(k^{2}+k)={\mathcal {O}}(k^{2})={\mathcal {O}}(log_{2}^{2}(n))}$ assuming ${\displaystyle n}$ comparisons can be performed in parallel.

Although the absolute number of comparisons is typically higher than Batcher's odd-even sort, many of the consecutive operations in a bitonic sort retain a locality of reference, making implementations more cache-friendly and typically more efficient in practice ^[3].

See also

• Batcher odd–even mergesort
• Pairwise sorting network