@ Bitonic Sorting Theorem

Bitonic Sorting Theorem: An even-odd compare exchange on a shuffled bitonic sequence results in two mutually sorted sequences obtained by grouping, in order, the low then high outputs of the compare-exchanges.

Bitonic sequence: A bitonic sequence is a sequence which is first non-decreasing and then non-increasing, or can be circularly shifted to become such a sequence.

Mutually sorted: If sequences A and B are mutually sorted in the order AB, then the smallest element of B is greater than the largest element of A.

There are 2 operations that happen in sequence.

First a perfect shuffle is performed on the input bitonic sequence.

Next each even odd pair is compare-exchanged with the low order outputs being directed in order to one group, and the high order outputs to another group.

To prove the theorem on all natural numbers, the restricted case of 0-1 sequences shall be examined. Then once it can be proved that all biotonic 0-1 sequences are sorted by a network iteratively performing the operations described above, the 0-1 principal will show that such a network can sort any bitonic sequence of n natural numbers. Finally the fact that the network does sort all bitonic natural numbers sequences shall be used to establish that the bitonic sorting theorem is true.

Claim:

Let a={a_0,...a_n-1} be a bitonic 0-1 sequence of length n, where n is even.

After a shuffle, odd-even comparison, and low/high output grouping we have the sequence:

{b_0,...,b_(n/2)-1, c_0,...,c_(n/2)-1 } b_i <= c_j for all i,j.

b={b_0,...b_(n/2)-1}, c={c_0,...c_(n/2)-1}

b is bitonic.

c is bitonic.

b, and c are mutually sorted, with b as the lesser sequence, and c the greater sequence.

Proof:

*Note: In the following (1^i) represents 1 repeated i times in order, for example (1^3) = 111,

similarly with 0^i, so (1^2)(0^3)(1^1) represents 110001.

Binary bitonic sequences can only take one of 4 forms.

Either 0^n, 1^n, (0^i)(1^j)(0^k), (1^i)(0^j)(1^k) (i+j+k=n in the latter 2 cases).

Sequences of the form 0^n, 1^n are already sorted and cannot be made unsorted by any number of compare-exchanges, or swaps and so can be ignored (none of the above described operations will have any effect).

Examining the (0^i)(1^j)(0^k) case:

There are depending on the relative sizes of i,j, and k 4 possible cases of what sequences are formed when the original sequence is split around the n/2’th element.

Case 1:

0^(i)1^(x)

1^(y)0^(k)

where x+y=j, and i+k>=n/2, j<=n/2

If each element from the top row is compare-exchanged with the corresponding element in the bottom row, (odd-even compare exchange after fair shuffle) then the low and high outputs are grouped in order the resulting subsequences will be.

Low order outputs : 0^(n/2)

High order outputs : 1^(y)0^(n/2 - j)1^(x)

Both these sequences are bitonic, and mutually ordered, as prescribed.

Case 2:

0^(i)1^(x)

1^(y)0^(k)

where x+y=j, and j>=n/2, i+k<=n/2

If each element from the top row is compare-exchanged with the corresponding element in the bottom row, (odd-even compare exchange after fair shuffle) then the low and high outputs are grouped in order the resulting subsequences will be.

Low order outputs : 0^(i)1^(j - n/2)0^(k)

High order outputs : 1^(n/2)

Both these sequences are bitonic, and mutually ordered, as prescribed.

Case 3:

0^(n/2)

0^(i-n/2)1^(j)0^(k)

where i >=n/2, i+k+j-n/2 = n/2

If each element from the top row is compare-exchanged with the corresponding element in the bottom row, (odd-even compare exchange after fair shuffle) then the low and high outputs are grouped in order the resulting subsequences will be.

Low order outputs : 0^(n/2)

High order outputs : 0^(i-n/2)1^(j)0^(k)

Both these sequences are bitonic, and mutually ordered, as prescribed.

Case 4:

0^(i)1^(j)0^(k-n/2)

0^(n/2)

where k >=n/2, i+k+j-n/2 = n/2

If each element from the top row is compare-exchanged with the corresponding element in the bottom row, (odd-even compare exchange after fair shuffle) then the low and high outputs are grouped in order the resulting subsequences will be.

Low order outputs : 0^(n/2)

High order outputs : 0^(i)1^(j)0^(k-n/2)

Both these sequences are bitonic, and mutually ordered, as prescribed.

In all 4 cases the resulting sequences are bitonic and mutually ordered.

Examining the (1^i)(0^j)(1^k) Case:

There are depending on the relative sizes of i,j, and k 4 possible cases of what the sequences that are formed when the original sequence is split around the n/2’th element.

Case 1:

1^(i)0^(x)

0^(y)1^(k)

where x+y=j, and i+k>=n/2, j<=n/2

If each element from the top row is compare-exchanged with the corresponding element in the bottom row, (odd-even compare exchange after fair shuffle) then the low and high outputs are grouped in order the resulting subsequences will be.

Low order outputs : 0^(y)1^(n/2 - j)0^(x)

High order outputs : 1^(n/2)

Both these sequences are bitonic, and mutually ordered, as prescribed.

Case 2:

1^(i)0^(x)

0^(y)1^(k)

where x+y=j, and j>=n/2, i+k<=n/2

If each element from the top row is compare-exchanged with the corresponding element in the bottom row, (odd-even compare exchange after fair shuffle) then the low and high outputs are grouped in order the resulting subsequences will be.

Low order outputs : 0^(n/2)

High order outputs : 1^(i)0^(j - n/2)1^(k)

Both these sequences are bitonic, and mutually ordered, as prescribed.

Case 3:

1^(n/2)

1^(i-n/2)0^(j)1^(k)

where i >=n/2, i+k+j-n/2 = n/2

If each element from the top row is compare-exchanged with the corresponding element in the bottom row, (odd-even compare exchange after fair shuffle) then the low and high outputs are grouped in order the resulting subsequences will be.

Low order outputs : 1^(i-n/2)0^(j)1^(k)

High order outputs : 1^(n/2)

Both these sequences are bitonic, and mutually ordered, as prescribed.

Case 4:

1^(i)0^(j)1^(k-n/2)

1^(n/2)

where k >=n/2, i+k+j-n/2 = n/2

If each element from the top row is compare-exchanged with the corresponding element in the bottom row, (odd-even compare exchange after fair shuffle) then the low and high outputs are grouped in order the resulting subsequences will be.

Low order outputs : 1^(i)0^(j)1^(k-n/2)

High order outputs : 1^(n/2)

Both these sequences are bitonic, and mutually ordered, as prescribed.

In all 4 cases the resulting sequences are bitonic and mutually ordered.

In each of the cases above, at least half of the input bitonic sequence is “cleaned” (is fully composed of 0’s or 1’s). Therefore if the remaining “dirty” bitonic sequence is put through an analogous network until all sequences are “clean” the full output will be ‘clean’ in log(n) network levels.

Once every subsequence has been “cleaned” the 0-1 sequence is sorted.

Therefore by the 0-1 principal since we can sort any 0-1 bitonic sequence in log(n) steps of the network, we can also sort any bitonic natural number sequence in log(n) steps.

Claim:

Finally, it can be shown by contradiction that the bitonic theorem holds. As shown, a bitonic 0-1 sequence of length can be sorted in log(n) steps by repeated recursive application of the bitonic theorem. Furthermore, by applying the 0-1 principal it can be stated that the same is true of a bitonic natural number sequence.

Proof:

Suppose, that an application of the steps described in the bitonic theorem results in 2 subsequences at least one of which is not bitonic. If this were the case then a network such as the one described above could not be recursively applied to a natural number sequence as it has only been shown that bitonic natural number sequences can be sorted by the network. A trivial counterexample can show that non-bitonic natural number sequences cannot be sorted by this network, take the sequence S={1,3,2,4} applying the sorting network described above will not sort this sequence, it will return the same sequence S which is unsorted. But it has been shown that all bitonic natural number sequence input to the network, are infact sorted by the network, therefore an application of the steps described in the bitonic theorem must produce 2 bitonic sequences.

Suppose, that an application of the steps described in the bitonic theorem results in 2 subsequences which are not mutually sorted. Call the low order sequence L, and the high order sequence H. Since the sequences are not mutually ordered at least one number in the L (call it a) must be greater than the smallest number in H (call it b). Continue the recursive application of the bitonic theorem to these subsequences as described in the bitonic sort proof above, in log(n) steps the sequence will be sorted. However, in the recursive application of the algorithm if at some stage of the algorithm a low and high subsequence are output, elements in these subsequences are never again swapped with each other. Elements within each subsequence will only be sorted within that subsequence. In other words once at some stage elements are divided into low-order and high-order sequences no elements will ever be swapped between these two sequences. This means that if after log(n) steps of the network the sequence is fully sorted, all elements of L will still come before all elements of H. This means that a will come before b in the final sorted order, but this is a contradiction. Therefore after an application of the steps described in the bitonic theorem the sequences produced must be mutually ordered.

It has been shown that the bitonic theorem holds.

References:

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm

Intro To Algo C.L.R.S pgs(712-715)