Some performance tests of “quicksort” and descendants
- 1 March 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 17 (3), 143-152
- https://doi.org/10.1145/360860.360870
Abstract
Detailed performance evaluations are presented for six ACM algorithms: quicksort (No. 64), Shellsort (No. 201), stringsort (No. 207), “ TREESORT3 ” (No. 245), quickersort (No. 271), and qsort (No. 402). Algorithms 271 and 402 are refinements of algorithm 64, and all three are discussed in some detail. The evidence given here demonstrates that qsort (No. 402) requires many more comparisons than its author claims. Of all these algorithms, quickersort requires the fewest comparisons to sort random arrays.Keywords
This publication has 14 references indexed in Scilit:
- Proof of a recursive program: QuicksortThe Computer Journal, 1971
- Algorithms 402: Increasing the efficiency of quicksortCommunications of the ACM, 1970
- Increasing the efficiency of quicksortCommunications of the ACM, 1970
- Samplesort: A Sampling Approach to Minimal Storage Tree SortingJournal of the ACM, 1970
- Algorithm 271: quickersortCommunications of the ACM, 1965
- Algorithm 245: TreesortCommunications of the ACM, 1964
- Algorithm 207: stringsortCommunications of the ACM, 1963
- Certification of Algorithms 63, 64, 65: Partition, quicksort, findCommunications of the ACM, 1962
- QuicksortThe Computer Journal, 1962
- Algorithm 64: QuicksortCommunications of the ACM, 1961