Katajainen, J., Levcopoulos, C., and Petersson, O. (1989). Local Insertion Sort Revisited. Technical Report LiTH-IDA-R-89-20, Department of Computer and Information Science, Linköping University, Sweden. Also presented at the International Symposium on Optimal Algorithms, Varna, Bulgaria, May 29 - June 2, 1989. (bibtex),
Abstract: Two measures of presortedness, Dist(X) and logDist(X), are presented. The measures are motivated by a geometric interpretation of the input sequence X. Using these measures, an exact characterization of the local insertion sort algorithm of Mannila is achieved. Variants of local insertion sort, using many fingers (i.e., pointers into a finger search tree) instead of only one, are suggested. The number can either be fixed beforehand or dynamic, i.e., vary during the sorting process. Different strategies for moving the fingers yield different algorithms. Some general conditions which all strategies should satisfy are stated, and two such strategies are given. Furthermore, a method for designing dynamic algorithms that allocate an optimal number of fingers is provided. For any specific strategy satisfying our conditions, this method yields an optimal algorithm.
CS Dept TR Overview