**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Sat, 22 Nov 2014 22:23:06 *

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.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*