Some Performance Tests of "quicksort" and Descendants

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.

CACM March, 1974

Loeser, R.

sorting, in-place sorting, sorting efficiency,
sorting performance tests, quicksort, quickersort, 
qsort, Shellsort, stringsort, TREESORT3,utility sort
algorithm, general-purpose sort algorithm, sorting 
algorithm documentation

4.49 5.31

CA740304 JB January 18, 1978  11:26 AM

1175	4	2679
1663	4	2679
1919	4	2679
1919	4	2679
1919	4	2679
1969	4	2679
1969	4	2679
1997	4	2679
1997	4	2679
2042	4	2679
2042	4	2679
2118	4	2679
2191	4	2679
2195	4	2679
2216	4	2679
2216	4	2679
2222	4	2679
2222	4	2679
2356	4	2679
2388	4	2679
2348	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2679	4	2679
2844	4	2679
2972	4	2679
3054	4	2679
3054	4	2679
3054	4	2679
3054	4	2679
3121	4	2679
970	5	2679
1175	5	2679
1190	5	2679
1228	5	2679
1969	5	2679
1997	5	2679
308	5	2679
2042	5	2679
2679	5	2679
2679	5	2679
2679	5	2679
507	5	2679
3054	5	2679
3187	5	2679
716	5	2679
783	5	2679
1175	6	2679
1880	6	2679
1919	6	2679
1969	6	2679
1980	6	2679
1997	6	2679
307	6	2679
308	6	2679
309	6	2679
2017	6	2679
2679	6	2679
776	6	2679