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

## IDA Technical Reports: abstract

*Generated: Wed, 01 Oct 2014 16:16:00 *

Levcopoulos, C. and Petersson, O. (1989).
**An Optimal Parallel Algorithm for Sorting Presorted Files**.
Technical Report LiTH-IDA-R-89-16, Department of Computer and Information
Science, Linköping University, Sweden.
A previous version presented at the 8th Conference on Foundations of Software
Technology and Theoretical Computer Science, Poona, India, Dec. 1988.
(bibtex),

**Abstract: **We present a cost optimal parallel algorithm for
sorting presorted files. The measure of presortedness we consider is the
number of inversions in the input file. The algorithm sorts a file of length
n, with 0(mn) inversions, in 0(log n(log*n-log*m)) time, provided 0(n log
m/(log n(log*n log* m))) processors are available, in the EREW PRAM model.
This is the first PRAM sorting algorithm which is cost optimal, with respect
to the number of inversions. Our method uses a new approach, which can also
be used to derive a simple sequential sorting algorithm, which is efficient
with respect to the number of inversions.

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

*<webmaster@ida.liu.se>*