"Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise."

Bodo Manthey, Till Tantau (2007)
a service of  Schloss Dagstuhl - Leibniz Center for Informatics