%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 }