@techreport{R-89-17,
TITLE = {A Note on Adaptive Parallel Sorting},
AUTHOR = {Christos Levcopoulos and Ola Petersson },
YEAR = {1989},
NUMBER = {R-89-17},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-17+abstr},
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.},
IDANR = {LiTH-IDA-R-89-17}