Sorting networks

Bitonic sorting network for n not a power of 2

 up

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.

Problem

The bitonic sorting network for a sequence of n = 2k 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(2k)
Figure 1: Block structure of bitonic sort(2k)

Basic definitions

Definition:  Let a = a0, ..., an-1 with n element natural numbers0 be a 0-1-sequence.

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

a0, ..., an-1 = 0.

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

a0, ..., an-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 element {0, ..., n} such that

a0, ..., ak-1 = 0 ,     ak, ..., an-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 element {0, ..., n} such that

a0, ..., ak-1 = 1 ,     ak, ..., an-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 element {0, ..., n} such that

a0, ..., ak-1 = 0 ,     ak, ..., am-1 = 1 ,     am, ..., an-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 element {0, ..., n} such that

a0, ..., ak-1 = 1 ,     ak, ..., am-1 = 0 ,     am, ..., an-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
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.

Idea

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

Figure 3: Comparator network Bn applied to bitonic decreasing 0-1-sequence a of length n
Figure 3: Comparator network Bn applied to bitonic decreasing 0-1-sequence a of length n

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

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 Bp applied to it yields two bitonic halves b and c', where |b| = p/2 and biless or equalc'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 Bp that do not belong to Bn are superfluous, therefore Bn applied to sequence a yields the same result.

By this theorem, recursive application of networks Bp where p is a power of 2 for the bitonic sequence b, and of networks Bn 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
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.

Program

The following program implements bitonic sort for arbitrary input length n element natural numbers.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;
    }

}

Network

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
Figure 5: Bitonic sorting network for input length n = 6

Analysis

The new sorting network for arbitrary n can be embedded into an original bitonic sorting network for 2k. Therefore, it also consists of  open ceilinglog(n)close ceiling · (open ceilinglog(n)close ceiling + 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.

References

[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.

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 07.12.1998   Updated: 14.03.2017
Valid HTML 4.01 Transitional