An adaptive generic sorting algorithm that uses variable partitioning
Vladimir Estivill‐Castro, D. Wood · 2002
Presents 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 algorithm that simplifies implementations.>