The diagram below shows a small Bitonic Sorting example with \(N=16\) elements. The network consists of \(q=10\) rounds of butterfly comparisons. These rounds are collected into $\log_2(N)=4$ stages, where there are a different number of rounds per stage. Stage 0 consists of 1 round, Stage 1 consists of 2 rounds, Stage 2 consists of 3 rounds and Stage 4 consists of 4 rounds. The figure highlights in yellow output samples from that stage whos ordering has not been affected, and highlights in red output samples from that stage whos ordering has been affected.
Notice how some identical rounds are included in each stage of processing. For example, the last two rounds of Stage 2 and Stage 3 contain identical processing. This fact is used in the second example below to construct Bitonic Sorting designs for larger \(N\).
The Bitonic Sorting algorithm works using the following “divide-and-conquer” approach. Each processing stage performs reording of samples in a local fashion with an increasing “span”:
Stage 0 performs 1 round of butterfly comparisons to output consecutive 2-tuples in sorted order.
Stage 1 performs 2 rounds of butterfly comparisons to output consecutive 4-tuples in sorted order.
Stage 2 performs 3 rounds of butterfly comparisons to output consecutive 8-tuples in sorted order.
Stage 3 performs 4 rounds of butterfly comparisons to output consecutive 16-tuples in sorted order.
After all stages of processing, the output of the final round is presented in fully sorted order.