Vitter, Jeffrey ScottNodine, Mark H.2011-03-212011-03-211993J. S. Vitter and M. H. Nodine. “Large-Scale Sorting in Uniform Memory Hierarchies,” special issue on parallel I/O systems in Journal of Parallel and Distributed Computing, 17, January 1993, 107–114. An extended abstract appears in “Large-Scale Sorting in Parallel Memories,” Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’91), Hilton Head, SC, July 1991, 29–39. http://dx.doi.org/10.1006/jpdc.1993.1008https://hdl.handle.net/1808/7211We present several e cient algorithms for sorting on the uniform memory hierarchy (UMH), introduced by Alpern, Carter, and Feig, and its paral- lelization P-UMH.We give optimal and nearly-optimal algorithms for a wide range of bandwidth degradations, including a parsimonious algorithm for constant bandwidth. We also develop optimal sorting algorithms for all bandwidths for other versions of UMH and P-UMH, including natural restrictions we introduce called RUMH and P-RUMH, which more closely correspond to current programming languages.en-USArticle10.1006/jpdc.1993.1008openAccess