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 comparators and have a delay of , where 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.
Imagem: MrTroble · BY-SA · Openverse
A bitonic sorter for k = 1 {\displaystyle k=1} ( n = 2 ) {\displaystyle (n=2)} is simply a comparator. This is illustrated by the given box layout, in which X and Y represent the inputs, while H and L represent the higher and lower outputs, respectively. With the sorter for k = 1 {\displaystyle k=1} , we can recursively create a sorter of higher order. For example, consider the following k = 2 {\displaystyle k=2} ( n = 4 ) {\displaystyle (n=4)} bitonic sorter. The bitonic sorter consists of two layers: a recombination layer, which recombines the bitonic inputs into two new bitonic sequences that are each half as long as the original sequence, and a bitonic sort layer consisting of two bitonic sorters of order k − 1 {\displaystyle k-1} , each of which sorts one of the two bitonic sequences produced by the previous layer. This structure may be extended recursively for higher values of k {\displaystyle k} by ensuring that each comparator always accepts one input from each of the two halves of the bitonic sequence it is meant to help sort. The following illustration depicts these connections schematically.
Correctness of the bitonic sorter
Ken Batcher provided some mathematical proof sketch in his paper. Without loss of generality the bitonic input sequence is assumed to be a 1 ≤ a 2 ≤ ⋯ ≤ a j − 1 ≤ a j ≥ a j + 1 ≥ ⋯ ≥ a 2 n {\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 1 ≤ j ≤ 2 n {\displaystyle 1\leq j\leq 2n} . With out loss of generality the sequence can be reversed therefore, we can assume n ≤ j ≤ 2 n {\displaystyle n\leq j\leq 2n} . Case 1: If a n ≤ a 2 n {\displaystyle a_{n}\leq a_{2n}} then every element of the two subsequences are smaller. In this case d i = a i {\displaystyle d_{i}=a_{i}} and e i = a n + i {\displaystyle e_{i}=a_{n+i}} with 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n} and therefore d i {\displaystyle d_{i}} and e i {\displaystyle e_{i}} are trivially bitonic.
Imagem: MrTroble · BY-SA · Openverse
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 n = 4 {\displaystyle n=4} bitonic sort network. The bitonic sorting network for k = 2 {\displaystyle k=2} can be created by using a k = 2 {\displaystyle k=2} bitonic sorter and two k = k p r e v − 1 {\displaystyle k=k_{prev}-1} sorters. The two sorters create a decreasingly or increasingly 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 k = 1 {\displaystyle k=1} networks; hence, they are just a comparator. The following figure shows the overall scheme.
Imagem: MrTroble · BY-SA · Openverse
The following pseudocode describes the sorting process. In the code, a is the array to be sorted, low is the index of the first item in the sub-array to be sorted, k and count is the number items in the sub-array that are being sorted in this function call. direction is a boolean value that determines whether the sub-array is being sorted into ascending / descending order. The function call bitonicSort(a, 0, n, 1) is used to sort a (ascending), where n is the number of items in a .
In this section we assume that our sorter has n = 2 k {\displaystyle n=2^{k}} input elements as previously. Each recursion in a bitonic sorting network adds a sorter of order k n e x t = k p r e v − 1 {\displaystyle k_{next}=k_{prev}-1} , which consists of bitonic k n e x t {\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 k {\displaystyle k} levels per bitonic sorter. Therefore, we can describe this construction's levels as the following sum: ∑ i = 1 k i {\displaystyle \sum _{i=1}^{k}i} . This sum can be reduced using the Gauss sum formula ∑ i = 1 k i = 1 2 k ( k + 1 ) {\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 1 2 k ( k + 1 ) {\displaystyle {\dfrac {1}{2}}k(k+1)} . Which gives us O ( k 2 + k ) = O ( k 2 ) = O ( ( log 2 n ) 2 ) {\displaystyle {\mathcal {O}}(k^{2}+k)={\mathcal {O}}(k^{2})={\mathcal {O}}((\log _{2}n)^{2})} assuming n {\displaystyle n} comparisons can be performed in parallel.
