The analysis of Quicksort programs

Robert Sedgewick

Research output: Contribution to journalArticlepeer-review

91 Scopus citations


The Quicksort sorting algorithm and its best variants are presented and analyzed. Results are derived which make it possible to obtain exact formulas describing the total expected running time of particular implementations on real computers of Quicksort and an improvement called the median-of-three modification. Detailed analysis of the effect of an implementation technique called loop unwrapping is presented. The paper is intended not only to present results of direct practical utility, but also to illustrate the intriguing mathematics which arises in the complete analysis of this important algorithm.

Original languageEnglish (US)
Pages (from-to)327-355
Number of pages29
JournalActa Informatica
Issue number4
StatePublished - Dec 1977

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'The analysis of Quicksort programs'. Together they form a unique fingerprint.

Cite this