Bitonic Sorting Network

A sequence that monotonically increases and then monotonically decreases, or else monotonically decreases and then monotonically increases is called a bitonic sequence. For example: the sequence (2, 5, 6, 9, 3, 1) and (8, 7, 5, 2, 4, 6) are both bitonic. The bitonic sorter is a comparison network that sorts bitonic sequence of 0's and 1's.

Half-Cleaner: A bitonic sorter is containing several stages, each of which is called a half-cleaner. Each half-cleaner is a comparison network of depth 1 in which input line i is compared with line 1+ for i = 1, 2......

When a bitonic sequence of 0's and 1's is practiced as input to a half-cleaner, the half-cleaner produces an output sequence in which smaller values are in the top half, larger values are in the bottom half, and both halves are bitonic, and at least one of the halves is clean.

Bitonic Sorter: By recursively connecting half-cleaners, we can build a bitonic sorter, which is a network that sorts bitonic sequences. The first stage of BITONIC-SORTER [n] consists of HALF-CLEANER [n], which produces two bitonic sequences of half the size such that every element in the top half is at least as small as each element in the bottom half. Thus, we can complete the sort by utilizing two copies of BITONIC-SORTER [n/2] to sort the two halves recursively.

Fig: The depth D (n) of BITONIC-SORTER [n] is given by recurrence whose solution is D (n) = log n.