Title :
On the Bit-Level Complexity of Bitonic Sorting Networks
Author :
Al-Hajery, Majed Z. ; Batcher, Kenneth E.
Author_Institution :
Kent State University, USA
Abstract :
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.
Keywords :
Computer science; Costs; Mathematics; Network topology; Parallel processing; Sorting;
Conference_Titel :
Parallel Processing, 1993. ICPP 1993. International Conference on
Conference_Location :
Syracuse, NY, USA
Print_ISBN :
0-8493-8983-6
DOI :
10.1109/ICPP.1993.126
