Research and Advances

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.

Advertisement

Author Archives

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved