A note on adaptive parallel sorting (Q582114)

We present a cost optimal parallel algorithm for sorting presorted sequences. The measure of presortedness we consider is Rem, i.e., the smallest number of elements whose removal 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+r \log 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.