@inproceedings{ea6c7c7d4cea4b339fa61f56f404f8fa,

title = "TIGHT COMPLEXITY BOUNDS FOR PARALLEL COMPARISON SORTING.",

abstract = "The time complexity of sorting n elements using p greater than equivalent to n processors on L. G. Valiant's (1975) parallel comparison tree model is considered. It is shown that this time complexity is THETA (log n/log(1 plus p/n)). For every fixed time k it is shown that OMEGA (n**1** plus **1 **/ **k ) comparisons are required and that there exists a randomized algorithm for comparison sort in time k with an expected number of O(n**1** plus **1 **k comparisons. This implies that for every fixed k, any deterministic comparison sort algorithm must be asymptotically worse than this randomized algorithm. It is shown that 'approximate sorting' in time 1 requires asymptotically more than n log n processors.",

author = "Noga Alon and Yossi Azar and Uzi Vishkin",

note = "Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "1986",

doi = "10.1109/sfcs.1986.57",

language = "English (US)",

isbn = "0818607408",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "IEEE",

pages = "502--510",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

}