Quicksort superiority over Heap Sort

Question

Heap Sort has a worst case complexity is O(nlog) n wnile Quicksort is O(n^2). But emperical evidences say quicksort is superior. Why is that??

Answer 1

Here's a couple explanations:

http://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html

http://users.aims.ac.za/~mackay/sorting/sorting.html

Essentially, even though the worst case for quick sort is O(n^2) it on average will perform better. :-)

Answer 2

Average-case complexity, and the fact that you can take simple steps to minimize the risk of worst-case complexity in Quicksort (e.g. select the pivot as a median of three elements rather than a single selected position).

Answer 3

One of the major factors is that quicksort has better locality of reference -- the next thing to be accessed is usually close in memory to the thing you just looked at. By contrast, heapsort jumps around significantly more. Since things that are close together will likely be cached together, quicksort tends to be faster.

However, quicksort's worst-case performance is significantly worse than heapsort's is. Because some critical applications will require guarantees of speed performance, heapsort is the right way to go for such cases.

Answer 4

Well let's see.. from http://www.sorting-algorithms.com/

Heap Sort (random)

Quick Sort (random)

Answer 5

The big-O notation means that the time required to sort n items is bounded above by the function c*n*log(n), where c is some unspecified constant factor. There is no reason why the constant c should be the same for quicksort and heapsort. So the real question is: why would you expect them to be equally fast?

Quicksort has always been somewhat faster than heapsort in practice, but the difference has become larger recently since, as mentioned before, locality of memory access has become so important to execution speed.