Quick(er)sort and optimal adaptivity

We use a robust measure of presortedness, based on the notion of $α$-sorted sub-sequences, to show that Quicksort, in general, Partition sort, is optimal for a much broader class of inputs than those captured by worst-case analysis. Our result also generalizes the well-known result on sorting multis