Sorting networks
Bitonic sort
Bitonic sort [Bat 68] is one of the fastest sorting networks. A sorting network [Knu 73][CLRS 01] is a special kind of sorting algorithm, where the sequence of comparisons is not data-dependent. This makes sorting networks suitable for implementation in hardware or in parallel processor arrays.
The sorting network bitonic sort consists of Θ(n·log(n)2) comparators. It has the same asymptotic complexity as odd-even mergesort and shellsort. Although a sorting network with only O(n·log(n)) comparators is known [AKS 83], due to its large constant it is slower than bitonic sort for all practical problem sizes.
In the following, bitonic sort is developed on the basis of the 0-1-principle [Knu 73][CLRS 01]. The 0-1-principle states that a comparator network that sorts every sequence of 0's and 1's is a sorting network, i.e. it sorts every sequence of arbitrary values.
Basic concepts
Definition: A sequence a = a0, ..., an-1 with ai ∈ {0, 1}, i = 0, ..., n-1 is called 0-1-sequence.
A 0-1-sequence is called bitonic,1) if it contains at most two changes between 0 and 1, i.e. if there exist subsequence lengths k, m ∈ {1, ..., n} such that
a0, ..., ak-1 = 0 , ak, ..., am-1 = 1 , am, ..., an-1 = 0 or
a0, ..., ak-1 = 1 , ak, ..., am-1 = 0 , am, ..., an-1 = 1
In the following figure, different examples of bitonic 0-1-sequences are outlined, where 0's are drawn white and 1's gray.
Figure 1: Some examples of bitonic 0-1-sequences
Definition: Let n ∈ ℕ, n even. The comparator network Bn is defined as follows:
Bn = [0 : n/2] [1 : n/2+1] ... [n/2-1 : n-1] (see example of Figure 2)
Example:
Figure 2: Comparator network B8
Theorem: Let a = a0, ..., an-1 be a bitonic 0-1-sequence, where n ∈ ℕ, n even. Application of comparator network Bn to a yields
Bn(a) = b0, ..., bn/2-1 c0, ..., cn/2-1
where all bi are less than or equal to all cj , i.e.
bi≤cj for all i, j ∈ {0, ..., n/2-1}
and furthermore
b0, ..., bn/2-1 is bitonic and
c0, ..., cn/2-1 is bitonic.
Proof: Let a = a0, ..., an-1 be a bitonic 0-1-sequence. Written in two rows, the sequence looks like shown in the following figure. The sequence starts with 0's, continues with 1's, and ends with 0's (Figure 3a). Or it starts with 1's, continues with 0's, and ends with 1's (Figure 3b). The regions of 1's may overlap or not.
Figure 3: Bitonic 0-1-sequences (arranged in two rows)
Several other variations are possible (see Figure 4 below). Application of comparator network Bn corresponds to a comparison between upper and lower row. In each case, the result stated in the theorem is achieved: all bi are less than or equal to all cj and b is bitonic and c is bitonic (Figure 4):
Figure 4: Application of comparator network Bn to bitonic 0-1-sequences
Bitonic sorting network
The building blocks of the sorting network BitonicSort are comparator networks Bk with different k, where k is a power of 2. By using the divide-and-conquer strategy
, networks BitonicMerge and BitonicSort are formed.
First, a comparator network BitonicMerge is built that sorts a bitonic sequence. Due to the theorem, Bn produces two bitonic subsequences, where all elements of the first are smaller or equal than those of the second. Therefore, BitonicMerge can be built recursively as shown in Figure 5.
The bitonic sequence necessary as input for BitonicMerge is composed of two sorted subsequences, where the first is in ascending and the other in descending order. The subsequences themselves are sorted by recursive application of BitonicSort (Figure 6).
Figure 5: BitonicMerge(n)
Figure 6: BitonicSort(n)
In the following Figure 7, as an example the sorting network BitonicSort(8) is given. The bitonic sequence e in the middle will be sorted by recursive application of Bk. The sequence e is bitonic, since it is composed of two halves d and d' which are sorted in opposite directions. These again are formed from bitonic sequences a and a' etc.
Given an arbitrary 0-1-sequence as input to the comparator network, the assertions stated in the figure will hold.
Figure 7: Sorting network BitonicSort for n = 8
At the output of the comparator network, the 0-1-sequence is sorted. Now the 0-1-principle can be applied to the comparator network as a whole: since the network sorts every arbitrary 0-1-sequence, it will also sort every sequence of arbitrary values, hence it is a sorting network.
Analysis
In order to form a sorted sequence of length n from two sorted sequences of length n/2, there are log(n) comparator stages required (e.g. the 3 = log(8) comparator stages to form sequence i from d and d'). The number of comparator stages T(n) of the entire sorting network is given by:
T(n) = log(n) + T(n/2)
The solution of this recurrence equation is
T(n) = log(n) + log(n)-1 + log(n)-2 + ... + 1 = log(n) · (log(n)+1) / 2
Each stage of the sorting network consists of n/2 comparators. On the whole, these are Θ(n·log(n)2) comparators.
Program
In the following, an implementation of bitonic sort in Java is given. The program is encapsulated in a class BitonicSorter.2) With the statements
s.sort(b);
an array b of length n is sorted with bitonic sort. The length n must be a power of 2 (cf. bitonic sort for arbitrary n).
Function bitonicSort first produces a bitonic sequence by recursively sorting its two halves in opposite directions, and then calls bitonicMerge.
Function bitonicMerge recursively sorts a bitonic sequence in ascending order, if dir = ASCENDING, and in descending order otherwise. The sequence to be sorted starts at index position lo, the number of elements is n.
A comparator is modelled by the function compare, where the parameter dir indicates the sorting direction. If dir is ASCENDING and a[i] > a[j] is true or dir is DESCENDING and a[i] > a[j] is false then a[i] and a[j] are exchanged.
{
private int[] a;
// sorting direction:
private final static boolean ASCENDING=true, DESCENDING=false;
public void sort(int[] a)
{
this.a=a;
bitonicSort(0, a.length, ASCENDING);
}
private void bitonicSort(int lo, int n, boolean dir)
{
if (n>1)
{
int m=n/2;
bitonicSort(lo, m, ASCENDING);
bitonicSort(lo+m, m, DESCENDING);
bitonicMerge(lo, n, dir);
}
}
private void bitonicMerge(int lo, int n, boolean dir)
{
if (n>1)
{
int m=n/2;
for (int i=lo; i<lo+m; i++)
compare(i, i+m, dir);
bitonicMerge(lo, m, dir);
bitonicMerge(lo+m, m, dir);
}
}
private void compare(int i, int j, boolean dir)
{
if (dir==(a[i]>a[j]))
exchange(i, j);
}
private void exchange(int i, int j)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}
} // end class BitonicSorter
Conclusions
We have presented the bitonic sorting network and proved its correctness. With Θ(n·log(n)2) comparators this sorting algorithm is not optimal – the lower bound for sorting based on comparisons is in Ω(n·log(n)). There are sorting algorithms like e.g. heapsort that achieve this lower bound. Nevertheless bitonic sort is interesting for realization in hardware or parallel processor arrays, since its sequence of comparisons is fixed and not dependent on data. The algorithm can be adapted to arbitrary n being not necessarily a power of 2 (bitonic sort for arbitrary n).
References
[AKS 83] M. Ajtai, J. Komlos, E. Szemeredi: An
[Bat 68] K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, 307-314 (1968)
[CLRS 01] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2nd edition, The MIT Press (2001)
[Knu 73] D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)
1) The term bitonic is a technical term meaning that the sequence is twofold monotonic.
2) It is assumed that the class BitonicSorter implements an interface Sorter with the method sort. Otherwise, "implements Sorter" may be omitted.
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 05.03.1997 Updated: 05.02.2023