Batcher’s Bitonic sorter is a parallel sorting algorithm whose main operation is a technique for merging two Bitonic sequences. A Bitonic sequence is the concatenation of an ascending and a descending sequence of numbers. For example, 2, 4, 6, 8, 9, 24, 6, 3, 2, 0 is a Bitonic sequence. To sort a sequence of n numbers, the Batcher’s Bitonic sort algorithm proceeds as follows. The first step is to convert the n numbers into a Bitonic sequence with n=2 numbers in an increasing sub-sequence and n=2 numbers in a decreasing sub-sequence. This is done recursively. After the Bitonic sequence with n numbers is obtained, it is merged into an ordered sequence (either increasing or decreasing, depending upon which is needed). The merging technique consists of log n stages, and each stage consists of three operations: shuffle, compare, and un-shuffle.
The Bitonic sorter constitutes of two type of basic blocks, BN and BN1. Both these blocks are shown below in Figure 1 and 2 respectively. BN block arranges two inputs in descending order and BN1 block arranges two inputs in ascending order.
The Bitonic sorter for eight inputs (n=8) is shown in Figure 3. Here, total 24 blocks are used. This sorter is shown for ascending order. Here x is the unsorted array and y is the sorted array in ascending order. The descending Bitonic sorter can be designed by exchanging the BN and BN1 blocks.
