Why is quicksort faster in average than others?

Question

As we know, the quicksort performance is O(n*log(n)) in average but the merge- and heapsort performance is O(n*log(n)) in average too. So the question is why quicksort is faster in average.

Answer 1

Wikipedia suggests:

Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Although quicksort is not an in-place sort and uses auxiliary memory, it is very well suited to modern computer architectures.

Also have a look at comparison with other sorting algorithms on the same page.

See also Why is quicksort better than other sorting algorithms in practice? on the CS site.

Answer 2

Worst case for quick sort is actually worse than heapsort and mergesort, but quicksort is faster on average.

As to why, it will take time to explain and thus i will refer to Skiena, The algorithm design manual.

A quote that summarizes the quicksort vs merge/heapsort:

When faced with algorithms of the same asymptotic complexity, implementation details and system quirks such as cache performance and memory size may well prove to be the decisive factor. What we can say is that experiments show that where a properly implemented quicksort is implemented well, it is typically 2-3 times faster than mergesort or heapsort. The primary reason is that the operations in the innermost loop are simpler. But I can’t argue with you if you don’t believe me when I say quicksort is faster. It is a question whose solution lies outside the analytical tools we are using. The best way to tell is to implement both algorithms and experiment.

Answer 3

Timsort might be a better option as it is optimised for the kind of data seen when sorting in general, in the Python language where data often contains embedded 'runs' of presorted items. It has lately been adopted by Java too.