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