Bitonic sorter

{{Short description|Parallel sorting algorithm}} {{Infobox Algorithm |name=Bitonic sorter|class=Sorting algorithm |image=250x250px |caption=Bitonic sorting network (bitonic merge sort) with 4 inputs with an example sequence that is being sorted. |data=Array |best-time= <math>\mathcal{O}((\log n)^2)</math> parallel time <ref name="bitonicReview">{{cite journal |last1=Megha |first1=Jain |last2=Sanjay |first2=Kumar |last3=V.K |first3=Patle |title=Bitonic Sorting Algorithm: A Review |journal=International Journal of Computer Applications |date=March 2015 |volume=113 |issue=13 |pages=40–43 |doi=10.5120/19890-1930 |bibcode=2015IJCA..113m..40J |url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=e8882ba90c9a3008158d431530cd16ba4fa4449a |access-date=14 May 2025 |ref=bitonicReview|doi-access=free }}</ref><ref name="bitonicImplSuperComputer">{{cite journal |last1=Ranković |first1=Vukašin |last2=Kos |first2=Anton |last3=Milutinović |first3=Veljko |title=Bitonic Merge Sort Implementation on the Maxeler Dataflow Supercomputing System |journal=The IPSI BGD Transactions on Internet Research |date=July 2013 |volume=9 |issue=2 |pages=5–10 |url=https://ipsitransactions.org/journals/papers/tir/2013july/p2.pdf |access-date=14 May 2025}}</ref> |average-time=<math>\mathcal{O}((\log n)^2)</math> parallel time<ref name="bitonicReview" /><ref name="bitonicImplSuperComputer" /> |time=<math>\mathcal{O}((\log n)^2)</math> parallel time<ref name="bitonicReview" /><ref name="bitonicImplSuperComputer" /> |space=<math>\mathcal{O}(n(\log n)^2)</math> non-parallel time<ref name="bitonicReview" /><ref name="bitonicImplSuperComputer" /> |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.<ref name=":0">{{cite book |last1=Batcher |first1=K. E. |chapter=Sorting networks and their applications |title=Proceedings of the April 30--May 2, 1968, spring joint computer conference on - AFIPS '68 (Spring) |date=30 April 1968 |pages=307–314 |doi=10.1145/1468075.1468121}}</ref> The resulting sorting networks consist of <math>\mathcal{O}(n(\log n)^2)</math> comparators and have a delay of <math>\mathcal{O}((\log n)^2)</math>, where <math>n</math> is the number of items to be sorted.<ref name="bitonicReview" /><ref name="bitonicImplSuperComputer" /> 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 <math>m</math> for which <math>x_0 \leq \cdots \leq x_m \geq \cdots \geq x_{n-1}.</math><ref name=":0" />

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 <math>n</math> is a perfect power of two. We will therefore let <math>k=\log_2(n)</math> be the integer for which <math>n = 2^k</math>, meaning that the bitonic sorters may be enumerated in order of increasing size by considering the successive values <math>k = 1, 2, 3, \ldots</math>.

== Bitonic Sorter ==

150x150px|thumb|alt=This image shows a comparator with two inputs labeled X and Y. And two outputs H and L|A normal comparator with two inputs

A bitonic sorter for <math>k=1</math> <math>(n=2)</math> is simply a comparator.<ref name=":0" /> 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 <math>k=1</math>, we can recursively create a sorter of higher order. For example, consider the following <math>k=2</math> <math>(n=4)</math> bitonic sorter.<ref name=":0" />

400px|frameless|center|alt=This image shows a bitonic merge sorter with 4 inputs. On the left are the inputs x1 to x4. These are connected to two comparators with x1 and x3 connected two one and x2 and x4 connected to the other. All low outputs go then into one comparator and all high outouts go into the other.|A <math>n=4</math> <math>(k=2)</math> bitonic merge 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 <math>k-1</math>, 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 <math>k</math> 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.<ref name=":0" />

400px|frameless|center|alt=test|test

As you can see, elements of the first half of the input sequence are pairwise compared against corresponding elements of the last half of the input sequence. 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. <ref name=":0" />

=== Correctness of the bitonic sorter ===

Ken Batcher provided some mathematical proof sketch in his paper.<ref name=":0" /> With out loss of generality the bitonic input sequence is assumed to be <math>a_1 \leq a_2 \leq \dots \leq a_{j-1} \leq a_j \geq a_{j+1} \geq \dots \geq a_{2n}</math> with <math>1 \leq j \leq 2n</math>. With out loss of generality the sequence can be reversed therefore, we can assume <math>n \leq j \leq 2n</math>.

'''Case 1''': If <math>a_n \leq a_{2n} </math> then every element of the two subsequences are smaller. In this case <math>d_i=a_i</math> and <math>e_i=a_{n+i}</math> with <math>1 \leq i \leq n</math> and therefore <math>d_i</math> and <math>e_i</math> are trivially bitonic.

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

'''''1'''''. For <math>1 \leq i \leq k</math> the sequences are <math>d_i=a_i</math> and <math>e_i=a_{n+i}</math>

'''''2'''''. For <math>k < i \leq 2n</math> the sequences are defined as the opposite of 1, with <math>d_i=a_{n+i}</math> and <math>e_i=a_i</math>

In the original paper he then claims the following inequalities result from those definitions:<ref name=":0" />

Following from '''''1''''': * For <math>1 \leq i \leq k</math> that <math>d_i \leq d_{i+1}</math> * For <math>j-n \leq i \leq k</math> that <math>e_i \geq e_{i+1}</math> * For <math>1 \leq i \leq j-n</math> that <math>e_i \leq e_{i+1}</math>

Following from '''''2''''': * For <math>k < i \leq 2n</math> that <math>d_i \geq d_{i+1}</math> * For <math>k < i \leq 2n</math> that <math>e_i \leq e_{i+1}</math>

From both: <math>e_n \leq e_1</math>

From the paper claims follows that the sequences <math>d_i</math> and <math>e_i</math> are in fact bitonic.<ref name=":0" />

== 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 <math>n=4</math> bitonic sort network.<ref name=":0" />

400px|frameless|center|alt=testa|test

The bitonic sorting network for <math>k=2</math> can be created by using a <math>k=2</math> bitonic sorter and two <math>k=k_{prev}-1</math> 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 <math>k=1</math> networks; hence, they are just a comparator.<ref name=":0" /> The following figure shows the overall scheme.

400px|frameless|center|alt=testa|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.

== Pseudocode == The following pseudocode describes the sorting process. In the code, <code>a</code> is the array to be sorted, <code>low</code> is the index of the first item in the sub-array to be sorted, <code>k</code> and <code>count</code> is the number items in the sub-array that are being sorted in this function call. <code>direction</code> is a boolean value that determines whether the sub-array is being sorted into ascending / descending order.

The function call <code>bitonicSort(a, 0, n, 1)</code> is used to sort <code>a</code> (ascending), where <code>n</code> is the number of items in <code>a</code> . '''function''' bitonicMerge(''a'', ''low'', ''count'', ''direction'') '''is''' '''if''' ''count'' > 1 '''THEN''' k ← ''count'' / 2 // Compare and swap elements across the halves '''for''' i ← ''low'' '''to''' ''low'' + k '''do''' // determine if two elements of ''a'' are out of order in relation to the direction of sorting. '''if''' (''direction'' == 1 '''AND''' ''a''[i] > ''a''[i + k]) '''OR''' (''direction'' == 0 '''AND''' ''a''[i] < ''a''[i + k]) THEN '''swap''' ''a''[i] '''with''' ''a''[i + k] // Recursively merge both halves '''bitonicMerge'''(''a'', ''low'', k, ''direction'') '''bitonicMerge'''(''a'', ''low'' + k, k, ''direction'') // This only works when input size is a power of 2. '''function''' bitonicSort(''a'', ''low'', ''count'', ''direction'') '''is''' '''if''' ''count'' > 1 '''THEN''' k ← ''count'' / 2 // Sort first/second half into ascending/descending order '''bitonicSort'''(''a'', ''low'', k, 1) '''bitonicSort'''(''a'', ''low'' + k, k, 0) // Merge entire sequence in desired order '''bitonicMerge'''(''a'', ''low'', ''count'', ''direction'')

== Complexity ==

In this section we assume that our sorter has <math>n=2^k</math> input elements as previously.

Each recursion in a bitonic sorting network adds a sorter of order <math>k_{next}=k_{prev}-1</math>, which consists of bitonic <math>k_{next}</math> 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 <math>k</math> levels per bitonic sorter. Therefore, we can describe this construction's levels as the following sum: <math>\sum_{i=1}^{k} i</math>.

This sum can be reduced using the Gauss sum formula <math>\sum_{i=1}^{k} i = \dfrac{1}{2}k(k+1)</math>

Therefore, the number of levels in which each comparison can be done in parallel is given by <math>\dfrac{1}{2} k(k+1)</math>.<ref name=":0" /> Which gives us <math>\mathcal{O}(k^2+k)=\mathcal{O}(k^2)=\mathcal{O}((\log_2 n)^2)</math> assuming <math>n</math> 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.<ref name=":0" />

== References == {{reflist}}

==External links== *[https://www.inf.hs-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm A discussion of this algorithm] *[https://xlinux.nist.gov/dads/HTML/bitonicSort.html Reference code] at NIST *[https://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm Tutorial with animated pictures and working code]

Category:Sorting algorithms