Heap Sort has a worst case complexity of O(nlogn) while Quicksort has O(n^2).
But emperical evidences say quicksort is superior. Why is that?
Quicksort superiority over Heap Sort
Viewed 21945
6 Answers
As already said, quicksort has much better locality of reference compared to heapsort, but the worst case has a O(n^2) complexity.
std::sort is implemented using introspection sort: it runs quicksort most of the time, but it case it detects that the runtime will be bad because of the bad pivot selection, it switches to heap sort. In that case you get a guaranteed O(nlog(n)) complexity together with the speed of quicksort, which is picked almost every time.
Related