| 1 1 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| This paper provides an analysis of a natural k-round tournament over n = 2 k players, and demonstrates that the tournament possesses a surprisingly strong ranking property. The ranking property of this tournament is exploited by using it as a building block for efficient parallel sorting algorithms under a variety of different models of computation. Three important applications are provided. First, a sorting circuit of depth 7:44 logn is defined that sorts all but a superpolynomially small fraction of the n! possible input permutations. Second, a randomized sorting algorithm is given for the hypercube and related parallel computers (the butterfly, cube-connected cycles and shuffle-exchange) that runs in O(log n) word steps with very high probability. Third, a randomized algorithm is given for sorting n O(m)-bit records on an n log n node butterfly that runs in O(m+ log n) bit steps with very high probability. 1 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||