Skip to Main content Skip to Navigation
Journal articles

Quicksort algorithm again revisited

Abstract : We consider the standard Quicksort algorithm that sorts n distinct keys with all possible n! orderings of keys being equally likely. Equivalently, we analyze the total path length L(n) in a randomly built \emphbinary search tree. Obtaining the limiting distribution of L(n) is still an outstanding open problem. In this paper, we establish an integral equation for the probability density of the number of comparisons L(n). Then, we investigate the large deviations of L(n). We shall show that the left tail of the limiting distribution is much ''thinner'' (i.e., double exponential) than the right tail (which is only exponential). Our results contain some constants that must be determined numerically. We use formal asymptotic methods of applied mathematics such as the WKB method and matched asymptotics.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958926
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:47:40 PM
Last modification on : Thursday, August 1, 2019 - 2:12:40 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:01:36 PM

File

dm030202.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958926, version 1

Collections

Citation

Charles Knessl, Wojciech Szpankowski. Quicksort algorithm again revisited. Discrete Mathematics and Theoretical Computer Science, DMTCS, 1999, 3 (2), pp.43-64. ⟨hal-00958926⟩

Share

Metrics

Record views

150

Files downloads

1130