@techreport{R-89-21,
TITLE = {Heapsort - Adapted for Presorted Files},
AUTHOR = {Christos Levcopoulos and Ola Petersson },
YEAR = {1989},
NUMBER = {R-89-21},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-21+abstr},
ABSTRACT = {We provide a new sorting algorithm which is optimal with respect to several known, and new, measures of presortedness. A new such measure, called Osc(X), measures the oscillation within the input data. The measure has an interesting application in the sweep-line technique in computational geometry. Our algorithm is based on a new approach which yields space efficiency and it uses simple data structures. For example, after a linear time preprocessing step, the only data structures used are a static tree and a heap.},
IDANR = {LiTH-IDA-R-89-21},
NOTE = {Also presented at the 1989 Workshop on Data Structures and Algorithms, Ottawa, Canada, May 17-19, 1989}