Header menu link for other important links
A simple optimal randomized algorithm for sorting on the PDM
S. Rajasekaran,
Published in
Volume: 3827 LNCS
Pages: 543 - 552
The Parallel Disks Model (PDM) has been proposed to alleviate the I/O bottleneck that arises in the processing of massive data sets. Sorting has been extensively studied on the PDM model due to the fundamental nature of the problem. Several randomized algorithms are known for sorting. Most of the prior algorithms suffer from undue complications in memory layouts, implementation, or lack of tight analysis. In this paper we present a simple randomized algorithm that sorts in optimal time with high probablity and has all the desirable features for practical implementation. © Springer-Verlag Berlin Heidelberg 2005.
About the journal
Published in
Open Access
Impact factor