An Adaptive Generic Sorting Algorithm that Uses Variable Partitioning

A sorting algorithm is adaptive if its run time for inputs of the same size n varies smoothly from O(n) to O(n log n) as the disorder of the input varies. It is well accepted that files that are already sorted are often sorted again and that many files occur naturally in nearly sorted state. Recently, researchers have focused their attention on sorting algorithms that are optimally adaptive with respect to several measures of disorder, (since the type of disorder in the input is unknown), and illustrating a need to develop tools for constructing adaptive algorithms for large classes of measures. We present a generic sorting algorithm that uses divide-and-conquer in which the number of subproblems depends on the disorder of the input and for which we can establish adaptivity with respect to an abstract measure. We present applications of this generic algorithm obtaining optimal adaptivity for several specific measures of disorder. Moreover, we define a randomized version of our generic ..