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.
No takes yet. Share an insight, caveat, or question.
D. S. Hirschberg (1978) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: