On the Bit-Level Complexity of Bitonic Sorting Networks
Majed Z. Al-Hajery, Kenneth E. Batcher · 1993
Bitonic sorting networks can be implemented with a bit-level cost complexity of O(N log^2 N) using comparators with bit-level O(1) time and cost complexities. Items to be sorted are pipelined (worm-hole routed) bit-serially most-significant-bit first through the network. The cost complexity can be reduced to O(N log N) by recirculating items of length O(logN) through logN stages.