A fast probabilistic parallel sorting algorithm

1 October 1981

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 212-219
https://doi.org/10.1109/sfcs.1981.6

Abstract

We describe a probabilistic parallel algorithm to sort n keys drawn from some arbitrary total ordered set. This algorithm can be implemented on a parallel computer consisting of n RAMs, each with small private memory, and a common memory of size O(n) such that the average runtime is bounded by O(log n). Hence for this algorithm the product of time and number of processors meets the information theoretic lower bound for sorting.

Keywords

SORTING
PARALLEL ALGORITHMS
COMPUTATIONAL MODELING
DECISION TREES
CONCURRENT COMPUTING
RANDOM ACCESS MEMORY
MERGING
RUNTIME
WRITING
ARITHMETIC

This publication has 3 references indexed in Scilit:

New Parallel-Sorting Schemes
IEEE Transactions on Computers, 1978
Parallelism in Comparison Problems
SIAM Journal on Computing, 1975
Expected time bounds for selection
Communications of the ACM, 1975