Bitonic sort

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(2k)

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

Definition: Let a = a₀, ..., a_n-1 with n ∈ ℕ₀ 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₀, ..., a_n-1 = 0.

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

a₀, ..., 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₀, ..., 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₀, ..., 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₀, ..., 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₀, ..., 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 Bn applied to bitonic decreasing 0-1-sequence a of length n

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

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 ∈ ℕ.¹) 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)²) 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)

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

[up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 07.12.1998 Updated: 05.02.2023

Bitonic sort

Bitonic sorting network for n not a power of 2

Problem

Basic definitions

Idea

Program

Network

Analysis

References