Abstract
Quicksort was rst introduced in 1961 by Hoare. Many
variants have been developed, the best of which are
among the fastest generic sorting algorithms available,
as testied by the choice of Quicksort as the default
sorting algorithm in most programming libraries. Some
sorting algorithms are adaptive, i.e. they have a com-
plexity analysis which is better for inputs which are
nearly sorted, according to some specied measure of
presortedness. Quicksort is not among these, as it uses
(n log n) comparisons even when the input is already
sorted. However, in this paper we demonstrate em-
pirically that the actual running time of Quicksort is
adaptive with respect to the presortedness measure Inv.
Dierences close to a factor of two are observed be-
tween instances with low and high Inv value. We then
show that for the randomized version of Quicksort, the
number of element swaps performed is provably adap-
tive with respect to the measure Inv. More precisely,
we prove that randomized Quicksort performs expected
O(n(1 + log(1 + Inv=n))) element swaps, where Inv de-
notes the number of inversions in the input sequence.
This result provides a theoretical explanation for the
observed behavior, and gives new insights on the be-
havior of the Quicksort algorithm. We also give some
empirical results on the adaptive behavior of Heapsort
and Mergesort.