Transitional behaviors of the average cost of quicksort with median-of-(2t + 1)

Abstract

A fine analysis is given of the transitional behavior of the average cost of quicksort with median-of-three. Asymptotic formulae are derived for the stepwise improvement of the average cost of quicksort when iterating median-of-threek rounds for all possible values ofk. The methods used are general enough to apply to quicksort with median-of-(2t + 1) and to explain in a precise manner the transitional behaviors of the average cost from insertion sort to quicksort proper. Our results also imply nontrivial bounds on the expected height, “saturation level,” and width in a random locally balanced binary search tree.