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

James Allen Fill (The Johns Hopkins University)
Svante Janson (Uppsala University)


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 so count the number of bit comparisons.  On the other hand, the standard analyses of many other algorithms (such as Quicksort) are performed in terms of the number of key comparisons.  We introduce the prospect of a fair comparison between algorithms of the two types by providing an average-case analysis of the number of bit comparisons required by Quicksort. Counting bit comparisons rather than key comparisons introduces an extra logarithmic factor to the asymptotic average total.  We also provide a new algorithm, "BitsQuick", that reduces this factor to constant order by eliminating needless bit comparisons.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-22

Publication Date: June 6, 2012

DOI: 10.1214/EJP.v17-1812


  • Bindjeme, Patrick; Fill, James Allen. The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract), Proceedings of the 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, 2012, to appear, available from
  • Chung, Kai Lai. A Course in Probability Theory. Third edition. Academic Press, Inc., San Diego, CA, 2001. xviii+419 pp. ISBN: 0-12-174151-6 MR1796326
  • Dongarra, Jack; Sullivan, Francis. Guest editors' introduction: the top 10 algorithms, Computing in Science & Engineering 2 (2000), no. 1, 22--23.
  • Fill, James Allen. Distributional convergence for the number of symbol comparisons used by QuickSort, Annals of Applied Probability (2012, to appear, available from
  • Fill, James Allen; Janson, Svante. Smoothness and decay properties of the limiting Quicksort density function. Mathematics and computer science (Versailles, 2000), 53--64, Trends Math., Birkhäuser, Basel, 2000. MR1798287
  • Fill, James Allen; Janson, Svante. Quicksort asymptotics. Analysis of algorithms. J. Algorithms 44 (2002), no. 1, 4--28. MR1932675
  • Fill, James Allen; Janson, Svante. The number of bit comparisons used by Quicksort: an average-case analysis, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (New York), ACM, 2004, pp. 300--307 (electronic). MR2291065
  • Fill, James Allen; Nakama, Takéhiko. Analysis of the expected number of bit comparisons required by Quickselect. Algorithmica 58 (2010), no. 3, 730--769. MR2672478
  • Fill, James Allen; Nakama, Takéhiko. Distributional convergence for the number of symbol comparisons used by QuickSelect, Preprint available from available from, 2012.
  • Flajolet, Philippe; Gourdon, Xavier; Dumas, Philippe. Mellin transforms and asymptotics: harmonic sums. Special volume on mathematical analysis of algorithms. Theoret. Comput. Sci. 144 (1995), no. 1-2, 3--58. MR1337752
  • Flajolet, Philippe; Sedgewick, Robert. Analytic Combinatorics. Cambridge University Press, Cambridge, 2009. xiv+810 pp. ISBN: 978-0-521-89806-5 MR2483235
  • Gut, Allan. Probability: A Graduate Course. Springer Texts in Statistics. Springer, New York, 2005. xxiv+603 pp. ISBN: 0-387-22833-0 MR2125120
  • Hoare, C. A. R. Quicksort. Comput. J. 5 1962 10--15. MR0142216
  • Knessl, Charles; Szpankowski, Wojciech. Quicksort algorithm again revisited. Discrete Math. Theor. Comput. Sci. 3 (1999), no. 2, 43--63 (electronic). MR1685649
  • Knuth, Donald Ervin. The Art of Computer Programming. Vol. 3: Sorting and Searching, second ed., Addison-Wesley, 1998.
  • Mahmoud, Hosam M. Evolution of Random Search Trees. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1992. xii+324 pp. ISBN: 0-471-53228-2 MR1140708
  • Neininger, Ralph; Rüschendorf, Ludger. Rates of convergence for Quicksort. Analysis of algorithms. J. Algorithms 44 (2002), no. 1, 51--62. MR1932677
  • Régnier, Mireille. A limiting distribution for quicksort. RAIRO Inform. Théor. Appl. 23 (1989), no. 3, 335--343. MR1020478
  • Rosenthal, Haskell P. On the subspaces of $L^{p}$ $(p>2)$ spanned by sequences of independent random variables. Israel J. Math. 8 1970 273--303. MR0271721
  • Rösler, Uwe. A limit theorem for "Quicksort''. RAIRO Inform. Théor. Appl. 25 (1991), no. 1, 85--100. MR1104413
  • Roura, Salvador. Digital access to comparison-based tree data structures and algorithms. J. Algorithms 40 (2001), no. 1, 1--23. MR1841250
  • Vallée, Brigitte; Clément, Julien; Fill, James Allen; Flajolet, Philippe. The number of symbol comparisons in QuickSort and QuickSelect, Automata, languages and programming. Part I, Lecture Notes in Comput. Sci., vol. 5555, Springer, Berlin, 2009, pp. 750--763. MR2544890 (2012b:68231)

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.