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

IDA Technical Reports: abstract

Generated: Fri, 18 Apr 2014 23:42:03

Levcopoulos, C. and Petersson, O. (1989). Heapsort - Adapted for Presorted Files. Technical Report LiTH-IDA-R-89-21, Department of Computer and Information Science, Linköping University, Sweden. Also presented at the 1989 Workshop on Data Structures and Algorithms, Ottawa, Canada, May 17-19, 1989. (bibtex),

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.


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>