Tight complexity bounds for parallel comparison sorting

Abstract

The time complexity of sorting n elements using p ≥ n processors on Valiant's parallel comparison tree model is considered. The following results are obtained. 1. We show that this time complexity is Θ(logn/log(1+p/n)). This complements the AKS sorting network in settling the wider problem of comparison sort of n elements by p processors, where the problem for p ≤ n was resolved. To prove the lower bound, we show that to achieve time k ≤ logn, we need Ω(kn1+1/k) comparisons. Häggkvist and Hell proved a similar result only for fixed k. 2. For every fixed time k, we show that: (a) Ω(n1+1/k lognl/k) comparisons are required, (O(n1+1/k logn) are known to be sufficient in this case), and (b) there exists a randomized algorithm for comparison sort in time k with an expected number of O(n1+1/k) comparisons. This implies that for every fixed k, any deterministic comparison sort algorithm must be asymptotically worse than this randomized algorithm. The lower bound improves on Häggkvist-Hell's lower bound. 3. We show that "approximate sorting" in time 1 requires asymptotically more than nlogn processors. This settles a problem raised by M. Rabin.