HYPERCUBIC SORTING NETWORKS

This paper provides an analysis of a natural d-round tournament over n = 2(d) players and demonstrates that the tournament possesses a surpr isingly strong ranking property. The ranking property of this tourname nt is used to design efficient sorting algorithms for several models o f parallel computation: (i) a comparator network of depth c . lg n, c approximate to 7:44, that sorts the vast majority of the n! possible i nput permutations; (ii) an O(lg n)-depth hypercubic comparator network that sorts the vast majority of permutations; (iii) a hypercubic sort ing network with nearly logarithmic depth; (iv) an O(lg n)-time random ized sorting algorithm for any hypercubic machine (other such algorith ms have been previously discovered, but this algorithm has a significa ntly smaller failure probability than any previously known algorithm); and (v) a randomized algorithm for sorting n O(m)-bit records on an ( n lg n)-node omega machine in O(m + lg n) bit steps.