On tree-growing search strategies
Janice Lent, Hosam M. Mahmoud · The Annals of Applied Probability · 1996
Using the concept of a "tree-growing" search strategy, we prove that for most practical insertion sorting algorithms, the number of comparisons needed to sort n keys has asymptotically normal behavior. We prove and apply a sufficient condition for asymptotically normal behavior. The condition specifies a relationship between the variance of the number of comparisons and the rate of growth in height of the sequence of trees that the search strategy "grows."