Transitional behaviors of the average cost of quicksort with median-of-(2t+1)
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 avenge cost of quicksort when iterating median-of-three k rounds for all possible values of k. 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.
quicksort insertion sort binary search tree phase transition ordinary differential equation uniform asymptotics recurrence relations