A FRAMEWORK FOR ADAPTIVE SORTING

A sorting algorithm is adaptive if it sorts sequences that are close t o sorted faster than random sequences, where the distance is determine d by some measure of presortedness. Over the years several measures of presortedness have been proposed in the literature, but it has been f ar from clear how they relate to each other, We show that there exists a natural partial order on the set of measures, which makes it possib le to say that some measures are superior to others. We insert all kno wn measures of presortedness into the partial order, and thereby provi de a powerful tool for evaluating both measures and adaptive sorting a lgorithms. We further present a new measure and show that it is a maxi mal element in the partial order formed by all known measures, and thu s that any sorting algorithm that optimally adapts to the new measure also optimally adapts to all other known measures of presortedness. We have not succeeded in developing an optimal algorithm for the new mea sure; however, we present one that is optimal in terms of comparisons.