@techreport{R-89-16,
TITLE = {An Optimal Parallel Algorithm for Sorting Presorted Files},
AUTHOR = {Christos Levcopoulos and Ola Petersson },
YEAR = {1989},
NUMBER = {R-89-16},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-16+abstr},
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.},
IDANR = {LiTH-IDA-R-89-16},
NOTE = {A previous version presented at the 8th Conference on Foundations of Software Technology and Theoretical Computer Science, Poona, India, Dec. 1988}