ADAPTIVE BINARY SORTING SCHEMES AND ASSOCIATED INTERCONNECTION NETWORKS

Many routing problems in parallel processing, such as concentration an d permutation problems, can be cast as sorting problems. In this paper , we consider the problem of sorting on a new model, called an adaptiv e sorting network. We show that any sequence of n bits can be sorted o n this model in O(lg2 n) bit-level delay using O(n) constant fanin gat es. This improves the cost complexity of Batcher's binary sorters by a factor of O(lg2 n) while matching their sorting time. The only other network that can sort binary sequences in O(n) cost is the network ver sion of columnsort algorithm, but this requires excessive pipelining. In addition, using binary sorters, we construct permutation networks w ith O(n lg n) bit-level cost and O(lg3 n) bit-level delay. These resul ts provide the asymptotically least-cost practical concentrators and p ermutation networks to date. We note, of course, that the well-known A KS sorting network has O(lg n) sorting time and O(n lg n) cost, but th e constants hidden in these complexities are so large that our complex ities outperform those of the AKS sorting network until n becomes extr emely large.