OPTIMAL PARALLEL ALGORITHM FOR INTEGER SORTING.
Publication
, Journal Article
Reif, JH
Published in: Annual Symposium on Foundations of Computer Science (Proceedings)
January 1, 1985
A new parallel algorithm is given for integer sorting where the integer keys are restricted to at most polynomial magnitude. The algorithm costs only logarithmic time and is the first known where the product of the time and processor bounds are bounded by a linear function of the input size. These simultaneous resource bounds are asymptotically optimal. All previous known parallel sorting algorithms required at least a linear number of processors to achieve logarithmic time bounds and hence were nonoptimal by at least a logarithmic factor.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Annual Symposium on Foundations of Computer Science (Proceedings)
DOI
ISSN
0272-5428
Publication Date
January 1, 1985
Start / End Page
496 / 504
Citation
APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1985). OPTIMAL PARALLEL ALGORITHM FOR INTEGER SORTING. Annual Symposium on Foundations of Computer Science (Proceedings), 496–504. https://doi.org/10.1109/sfcs.1985.9
Reif, J. H. “OPTIMAL PARALLEL ALGORITHM FOR INTEGER SORTING.” Annual Symposium on Foundations of Computer Science (Proceedings), January 1, 1985, 496–504. https://doi.org/10.1109/sfcs.1985.9.
Reif JH. OPTIMAL PARALLEL ALGORITHM FOR INTEGER SORTING. Annual Symposium on Foundations of Computer Science (Proceedings). 1985 Jan 1;496–504.
Reif, J. H. “OPTIMAL PARALLEL ALGORITHM FOR INTEGER SORTING.” Annual Symposium on Foundations of Computer Science (Proceedings), Jan. 1985, pp. 496–504. Scopus, doi:10.1109/sfcs.1985.9.
Reif JH. OPTIMAL PARALLEL ALGORITHM FOR INTEGER SORTING. Annual Symposium on Foundations of Computer Science (Proceedings). 1985 Jan 1;496–504.
Published In
Annual Symposium on Foundations of Computer Science (Proceedings)
DOI
ISSN
0272-5428
Publication Date
January 1, 1985
Start / End Page
496 / 504