The Batcher Network uses the properties of a Bitonic Sequence. A sequence of values is called Bitonic if it has a minimum or maximum value surrounded by monotonically ascending or descending values. A completely ordered sequence of values, whether ascending or descending, is Bitonic, as are (trivially) sequences of 2 or fewer values, and (degenerately) completely ordered sequences.
The figure shows 2 Bitonic Sequences. Let us call the first of these sequences positive because it has a maximum. Let us call the second sequence negative because it has a minimum. A Bitonic Sequence of length N splits into 2 Bitonic Sequences of length N/2, with the property that every member of the first (positive) sequence is less than every member of the second (negative) sequence. Sequences A and B are split by comparing each pair of values Ai and Bi, and swapping them, if necessary.
After a split, each resulting Bitonic Sequence can again be split into 2 smaller Bitonic Sequences of length N/4 each. The last split results in pairs of Bitonic Sequence of length 1, but since they still have the property that every (i.e. the single) member of sequence A is less than every member of sequence B, all sequences are now in order. Thus each stage of a Batcher network uses LogN rows of comparators to sort N inputs.
A Batcher Network for M=8 inputs (see Peterson & Davie, page 199), sorts its inputs by repeating this process on pairs of inputs. It doubles the input size each time until the entire input is sorted. It cleverly arranges for each adjacent Bitonic Sequence to be sorted in alternately ascending and descending order, by using up (U) or down (D) comparators. Thus, each pair of adjacent ordered sequences of length N, forms a new Bitonic Sequence of length 2N.
It first orders adjacent pairs of inputs into alternately ascending and descending order. In this way, in its first stage, the Batcher Network creates N/4 Bitonic Sequences of length 4. These are input to the 2nd stage.
NOTE: The diagram above differs slightly from Figure 4.26 in Peterson & Davie because the 2 darkened comparators are drawn in swapped positions, although the wiring connections are the same. This makes inputs to, and outputs from stage 3, row 2 in the following table, appear in a different order from those which would appear using the Peterson & Davie diagram.
The following table summarizes the flow of input values to each stage and row of the M=8 Batcher Network:
Input: 7 6 3 2 5 4 1 0 Output from Stage 1: 6 7 3 2 4 5 1 0 Input to Stage 2, row 1: 3 2 6 7 4 5 1 0 Input to Stage 2, row 2 after row 1: 3 2 6 7 4 5 1 0 Output from Stage 2: 2 3 6 7 5 4 1 0 Input to Stage 3, row 1 after Stage 2: 2 5 3 4 6 1 7 0 Input to Stage 3, row 2 after row 1: 2 1 5 6 3 0 4 7 Input to Stage 3, row 3 after row 2: 1 0 2 3 5 4 6 7 Output from Stage 3: 0 1 2 3 4 5 6 7
The 2nd stage of a Batcher Network contains 2 rows of comparators. The first row of the 2nd stage re-arranges pairs of adjacent Bitonic Sequences of length 4 into resulting alternately negative and positive Bitonic Sequences of length 4, such that every member of the first sequence of a pair, is less than every member of the second sequence of the pair. The 2nd row of the 2nd stage rearranges each positive sequence of the N/4 Bitonic Sequences of length 4 into ascending order, and each negative sequence into descending order. The result is N/8 (alternately positive and negative) Bitonic Sequences of length 8.
In its last stage a Batcher Network for M inputs contains Log2M rows of comparators. In the diagram with M=8 inputs, therefore, the last stage contains 3 rows of comparators. The last stage simply re-arranges its single input Bitonic Sequence into a single ordered sequence. The first row of the last stage creates 1 pair of alternately positive and negative Bitonic Sequences in which the every member of the first sequence of a pair is less than every member of the second sequence of the pair. The 2nd row creates 2 pairs with this property. The 3rd row creates 4 pairs having this property. The result in our M=8 example is 4 pairs of values in ascending order, which is a completely sorted sequence.
In general, a Batcher Network for M inputs has Log2M stages with the i'th stage having i rows of comparators. With M/2 comparators per row, this gives a total of ½ × (Log2M)×(Log2M + 1)×M/2 comparators.