Alok Aggarwal, Dina Kravets, et al.
Algorithmica (New York)
We adapt the Sharesort algorithm of Cypher and Plaxton to run on various parallel models of multi-level storage, and analyze its resulting performance. Sharesort was originally defined in the context of sorting n records on an n-processor hypercubic network. In that context, it is not known whether Sharesort is asymptotically optimal. Nonetheless, we find that Sharesort achieves optimal time bounds for parallel sorting in multi-level storage, under a variety of models that have been defined in the literature.
Alok Aggarwal, Dina Kravets, et al.
Algorithmica (New York)
Tomas Feder, Nimrod Megiddo, et al.
SODA 1994
Robert E. Cypher, C.Greg Plaxton
STOC 1990
Alok Aggarwal, Bernard Chazelle, et al.
FOCS 1984