The number of bit comparisons used by Quicksort: an average-case analysis

James Allen Fill, Svante Janson

The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and…