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.
CS Dept TR Overview