Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 327-355 |
| Number of pages | 29 |
| Journal | Acta Informatica |
| Volume | 7 |
| Issue number | 4 |
| DOIs | |
| State | Published - Dec 1977 |
All Science Journal Classification (ASJC) codes
- Software
- Information Systems
- Computer Networks and Communications