A framework for simple sorting algorithms on parallel disk systems (extended abstract)
Sanguthevar Rajasekaran · 1998
In this paper we present a simple parallel sorting algorithm and illustrate two applications.The algorithm (called the (1, m)-merge sort (LMM)) is an extension of the bitonic and odd-even merge sorts.Literature on parallel sorting is abundant.Many of the algorithms proposed, though being theoretically important, may not perform satisfactorily in practice owing to large constants in their time bounds.The algorithm to be presented in this paper, due partly to its simplicity, results in small constants.We present an implementation for the parallel disk sorting problem.The algorithm is asymptotically optimal (assuming that N is a polynomial in M, where N is the number of records to be sorted and M is the internal memory size).The underlying constant is very small.This algorithm has a better performance than the disk-striped mergesort (DSM) algorithm when the number of disks is large.Our implementation is as simple as that of DSM (requiring no fancy data structures or prefetch techniques.)Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the fidl citation on the first page.TO copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific