## Sorting networks## Bitonic sorting network for n not a power of 2 |

The classical bitonic sorting network [Bat 68] is devised for the input length `n` being a power of 2. In the following, a bitonic sorting network for arbitrary `n` is proposed. Its correctness follows from application of the 0-1-principle.

The bitonic sorting network for a sequence of `n` = 2^{k} elements consists of three blocks shown in Figure 1. The first two blocks are bitonic sorting networks that sort the two halves of the sequence in ascending and, respectively, descending order. The third part is a bitonic merge network that merges the two sorted halves to obtain the sorted sequence.

Originally, the bitonic merge network is defined only for `n` a power of 2. In the following, a bitonic merge network for arbitrary `n` is proposed.

| |

Figure 1: Block structure of bitonic sort(2^{k}) | |

Definition: Let `a` = `a`_{0}, ..., `a`_{n-1} with `n` _{0} be a 0-1-sequence.

We say that `a` is a clean 0-sequence, if it consists of 0's only, i.e. if

`a`_{0}, ..., `a`_{n-1} = 0.

We say that `a` is a clean 1-sequence, if it consists of 1's only, i.e. if

`a`_{0}, ..., `a`_{n-1} = 1.

We say that `a` is monotonic increasing, if it consists of a clean 0-sequence followed by a clean 1-sequence, i.e. if there exists a subsequence length `k` {0, ..., `n`} such that

`a`_{0}, ..., `a`_{k-1} = 0 , `a`_{k}, ..., `a`_{n-1} = 1.

We say that `a` is monotonic decreasing, if it consists of a clean 1-sequence followed by a clean 0-sequence, i.e. if there exists a subsequence length `k` {0, ..., `n`} such that

`a`_{0}, ..., `a`_{k-1} = 1 , `a`_{k}, ..., `a`_{n-1} = 0.

We say that `a` is bitonic increasing, if it consists of a clean 0-sequence followed by a clean 1-sequence followed by a clean 0-sequence, i.e. if there exist subsequence lengths `k`, `m` {0, ..., `n`} such that

`a`_{0}, ..., `a`_{k-1} = 0 , `a`_{k}, ..., `a`_{m-1} = 1 , `a`_{m}, ..., `a`_{n-1} = 0

We say that `a` is bitonic decreasing, if it consists of a clean 1-sequence followed by a clean 0-sequence followed by a clean 1-sequence, i.e. if there exist subsequence lengths `k`, `m` {0, ..., `n`} such that

`a`_{0}, ..., `a`_{k-1} = 1 , `a`_{k}, ..., `a`_{m-1} = 0 , `a`_{m}, ..., `a`_{n-1} = 1

By this definition, a clean sequence may be considered as monotonic increasing as well as monotonic decreasing. Similarly, a monotonic sequence may be considered as bitonic increasing as well as bitonic decreasing. Figure 2 shows some examples of bitonic sequences, where white regions indicate 0's and gray regions indicate 1's. Arrows indicate special case relations (e.g. a clean 0-sequence is a special case of a monotonic decreasing sequence).

| |

Figure 2: Examples of bitonic sequences with special case relations | |

Theorem: Let `a` be a 0-1-sequence. If `a` has the property of being a clean 0-sequence / a clean 1-sequence / monotonic increasing / monotonic decreasing / bitonic increasing / bitonic decreasing, then any subsequence `a'` of `a` has the same property.

Standard bitonic sort uses a comparator network `B`_{p} where `p` is a power of 2 as the basic building block. We derive network `B`_{n} for arbitrary `n` from network `B`_{p} where `p` is the next-greatest power of 2 by using only the first `n` – `p`/2 comparators of `B`_{p}. Figure 3 shows a comparator network `B`_{n} for `n` = 6 embedded into `B`_{p} with `p` = 8. Only the first two comparators are used.

| |

Figure 3: Comparator network B_{n} applied to bitonic decreasing 0-1-sequence a of length n | |

Theorem: Let `n` , `n` not a power of 2, and `p`>`n` the next-greatest power of 2. Network `B`_{n} applied to a bitonic decreasing 0-1-sequence `a` yields sequences `b` and `c` with the following properties (Figure 3):

- |
`b`| =`p`/2, a power of 2, `b`_{i}`c`_{j}for all`i`,`j`,`b`is bitonic and`c`is bitonic decreasing.

Proof: If the bitonic decreasing input sequence `a` of length `n` is filled up with 1's to a sequence `a'` of length `p`, it remains bitonic decreasing. Network `B`_{p} applied to it yields two bitonic halves `b` and `c'`, where |`b`| = `p`/2 and `b`_{i}`c`'`j` for all `i`, `j` (see standard bitonic sort). Since the additional 1's remain at their positions, sequence `c'` ends with 1's and is therefore bitonic decreasing. Disregarding the additional 1's yields a subsequence `c` of `c'` that is bitonic decreasing, too. The comparators of `B`_{p} that do not belong to `B`_{n} are superfluous, therefore `B`_{n} applied to sequence `a` yields the same result.

By this theorem, recursive application of networks `B`_{p} where `p` is a power of 2 for the bitonic sequence `b`, and of networks `B`_{n} where `n` is an arbitrary number for the bitonic decreasing sequence `c` finally yields a sorted sequence.

If the sorting direction is descending instead of ascending, the same theorem holds with "bitonic increasing" instead of "bitonic decreasing". In the proof, the original sequence `a` is filled up with additional 0's instead of 1's.

Figure 4 shows the block structure of the bitonic sorting network for arbitrary input length `n`. Initially, bitonic sort for arbitrary `n` is used to sort the first half of the input sequence in descending order and the rest of the input sequence in ascending order. The result is a bitonic decreasing sequence which is then sorted by bitonic merge for arbitrary `n`. Since `n` may be an odd number, integer division is used to determine the first "half" of the sequence.

| |

Figure 4: Block structure of bitonic sort(n) for arbitrary input length n | |

Since the network sorts every 0-1-sequence, due to the 0-1-principle it sorts any sequence of arbitrary numbers.

The following program implements bitonic sort for arbitrary input length `n` .^{1}) With

```
Sorter s=new BitonicSorterForArbitraryN();
s.sort(b);
``` |

an array `b` is sorted with bitonic sort.

public class BitonicSorterForArbitraryN implements Sorter { private int[] a; private final static boolean ASCENDING=true; // sorting direction 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, !dir); bitonicSort(lo+m, n-m, dir); bitonicMerge(lo, n, dir); } } private void bitonicMerge(int lo, int n, boolean dir) { if (n>1) { int m=greatestPowerOfTwoLessThan(n); for (int i=lo; i<lo+n-m; i++) compare(i, i+m, dir); bitonicMerge(lo, m, dir); bitonicMerge(lo+m, n-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; } // n>=2 and n<=Integer.MAX_VALUE private int greatestPowerOfTwoLessThan(int n) { int k=1; while (k>0 && k<n) k=k<<1; return k>>>1; } } |

As an example, Figure 5 shows the bitonic sorting network for input length `n` = 6.

| |

Figure 5: Bitonic sorting network for input length n = 6 | |

The new sorting network for arbitrary `n` can be embedded into an original bitonic sorting network for 2^{k}. Therefore, it also consists of log(`n`) · (log(`n`) + 1) / 2 stages. Each stage consists of at most `n`/2 comparators. This results in a complexity of `O`(`n` log(`n`)^{2}) comparators, just as the original bitonic sorting network.

[Bat 68] | K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, 307-314 (1968) |

^{1}) It is assumed that an interface *Sorter* with the method *sort* is provided, otherwise "implements Sorter" in the class declaration may be omitted.

H.W. Lang Hochschule Flensburg lang@hs-flensburg.de Impressum © Created: 07.12.1998 Updated: 14.03.2017 |