Levcopoulos, C. and Petersson, O. (1989). A Note on Adaptive Parallel Sorting. Technical Report LiTH-IDA-R-89-17, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: We present a cost optimal parallel algorithm for sorting presorted sequences. The measure of presortedness we consider is Rem(X), i.e., the smallest number of elements whose removal from the input sequence X leaves a sorted sequence. The algorithm sorts a sequence X of length n, with Rem(X)=r, in O(log n) time, provided O((n+rlog r)/log n) processors are available, in the EREW PRAM model. This is the first PRAM sorting algorithm which is cost optimal, with respect to Rem(X). A sequential implementation of the algorithm turns out to be one of the simplest sorting algorithms which is optimal with respect to any measure of presortedness.
CS Dept TR Overview