Tight Complexity Bounds for Parallel Comparison Sorting

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.

Authors

• Noga Alon
• Yossi Azar
• Uzi Vishkin

Keywords

• Sorting
• Computer science
• Time measurement
• Phase change random access memory
• Decision trees
• Concurrent computing
• Mathematics
• Mathematical model
• Performance evaluation
• Read-write memory
• Parallel Comparison
• Parallel Sorting
• Deterministic
• Lower Bound
• Time Complexity
• Parallel Model
• Sorting Algorithm
• Upper Bound
• Independent Set
• Number Of Comparisons
• Model Algorithm
• Break Point
• Pair Of Elements
• Optimal Speed
• Parallel Algorithm
• Input Elements
• Explicit Algorithm