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 n1+1/k processors, for k an arbitrary integer. The model of computation for this procedure permits simultaneous fetches from the same memory location.
%0 Journal Article
%1 Hirschberg:1978:FPS:359576.359582
%A Hirschberg, D. S.
%C New York, NY, USA
%D 1978
%I ACM
%J Commun. ACM
%K algorithm cacm magazine parallel sorting
%N 8
%P 657--661
%R 10.1145/359576.359582
%T Fast Parallel Sorting Algorithms
%V 21
%X 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 n1+1/k processors, for k an arbitrary integer. The model of computation for this procedure permits simultaneous fetches from the same memory location.
@article{Hirschberg:1978:FPS: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 n1+1/k processors, for k an arbitrary integer. The model of computation for this procedure permits simultaneous fetches from the same memory location.},
acmid = {359582},
added-at = {2016-11-08T04:49:33.000+0100},
address = {New York, NY, USA},
author = {Hirschberg, D. S.},
biburl = {https://www.bibsonomy.org/bibtex/20ffb5d4d86ee9107da12bd6863e80a6e/ytyoun},
doi = {10.1145/359576.359582},
interhash = {b6439f7a4d1dd715b2aa8962e28519b6},
intrahash = {0ffb5d4d86ee9107da12bd6863e80a6e},
issn = {0001-0782},
issue_date = {Aug. 1978},
journal = {Commun. ACM},
keywords = {algorithm cacm magazine parallel sorting},
month = aug,
number = 8,
numpages = {5},
pages = {657--661},
publisher = {ACM},
timestamp = {2016-11-08T06:01:58.000+0100},
title = {Fast Parallel Sorting Algorithms},
volume = 21,
year = 1978
}