The Algorithm Design Manual Second Edition

129

4.6.3

Is Quicksort Really Quick?

There is a clear, asymptotic difference between an Θ(n log n) algorithm and one

that runs in Θ(n

2

). Thus, only the most obstinate reader would doubt my claim

that mergesort, heapsort, and quicksort should all outperform insertion sort or

selection sort on large enough instances.

But how can we compare two Θ(n log n) algorithms to decide which is faster?

How can we prove that quicksort is really quick? Unfortunately, the RAM model

and Big Oh analysis provide too coarse a set of tools to make that type of distinc-

tion. When faced with algorithms of the same asymptotic complexity, implemen-

tation details and system quirks such as cache performance and memory size may

well prove to be the decisive factor.