A bitonic sorting network with simpler flip interconnections

This paper presents the new scheme of interconnecting levels in a bitonic sorting network with simpler inter-level wiring. A parity technique which leads to the algorithm Construct-BSMF is introduced. Wiring simplification through the network is achieved wiring the N/2 even-parity keys straight through the network. N/2 odd-parity keys use flip interconnections. As a result, our interconnection scheme simplifies the inter-level wiring through the network and outperforms the perfect-shuffle interconnection scheme both in terms of cost and delay.