article · 1993
Fast deterministic approximate and exact parallel sorting
Cited by 17Open access
Abstract
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).
Cite this paper
Hagerup, T., & Raman, R. (1993). Fast deterministic approximate and exact parallel sorting. https://doi.org/10.1145/165231.157380
Hagerup, Torben, and Rajeev Raman. “Fast deterministic approximate and exact parallel sorting.” 1993, pp. 346–55, https://doi.org/10.1145/165231.157380.
Hagerup, Torben, and Rajeev Raman. 1993. “Fast deterministic approximate and exact parallel sorting.” https://doi.org/10.1145/165231.157380.
Hagerup, T. and Raman, R. (1993) ‘Fast deterministic approximate and exact parallel sorting’. Available at: https://doi.org/10.1145/165231.157380.
@article{hagerup1993fast,
title = {{Fast deterministic approximate and exact parallel sorting}},
author = {Hagerup, Torben and Raman, Rajeev},
pages = {346--355},
year = {1993},
doi = {10.1145/165231.157380}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.