Fast deterministic approximate and exact parallel sorting
Torben Hagerup, Rajeev Raman · 1993
Padded sorting requires n input keys to be output in sorted order in an array with slightly more than n locations, unused locations being filled with a special null value.We show that a deterministic CRCW PRAM with h processors can padded-sort n keys in ~(log log k)s .2°(*0g" '-lOg* '+1) time, for any k with 4 s k s n, which is close to a known lower bound of Q(log n/log k).As a consequence, we are able to improve the best previous result on deterministic sublogarithmic standard sorting.Other results include deterministic algorithms with optimal speedup for approximate prefix summation and for padded-sorting independent uniformly distributed random variables.In the first case the running time is O((log log n)4/log log log n), and in the second case the average running time is O((log log log n)4 /log(4) n).