Fast parallel sorting algorithms
- 1 August 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 21 (8), 657-661
- https://doi.org/10.1145/359576.359582
Abstract
A parallel bucket-sort algorithm is presented that requires time O (log n ) and the use of n processors. The algorithm makes use of a technique that requires more space than the product of processors and time. A realistic model is used in which no memory contention is permitted. A procedure is also presented to sort n numbers in time O ( k log n ) using n 1 + 1 / k processors, for k an arbitrary integer. The model of computation for this procedure permits simultaneous fetches from the same memory location.Keywords
This publication has 12 references indexed in Scilit:
- Parallel algorithms for the transitive closure and the connected component problemsPublished by Association for Computing Machinery (ACM) ,1976
- Merging with parallel processorsCommunications of the ACM, 1975
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974
- Parallelism in tape-sortingCommunications of the ACM, 1974
- Optimal algorithms for parallel polynomial evaluationJournal of Computer and System Sciences, 1973
- On the time required for a sequence of matrix productsCommunications of the ACM, 1973
- Cellular arrays for the solution of graph problemsCommunications of the ACM, 1972
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- Very high-speed computing systemsProceedings of the IEEE, 1966