Fast Parallel Sorting Algorithms 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 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. CACM August, 1978 Hirschberg, D. Parallel processing, sorting, algorithms, bucket sort 3.74 4.34 5.25 5.31 CA780803 DH February 7, 1979 10:25 AM 2714 4 3075 3075 4 3075 3075 4 3075 3075 4 3075 3075 4 3075 3085 4 3075 3156 4 3075 2289 5 3075 2557 5 3075 2664 5 3075 2714 5 3075 3075 5 3075 3075 5 3075 3075 5 3075 3156 5 3075 2289 6 3075 2973 6 3075 3075 6 3075