algorithmsortingquicksortheapsort

Quicksort vs heapsort


Both quicksort and heapsort do in-place sorting. Which is better? What are the applications and cases in which either is preferred?


Solution

  • This paper has some analysis.

    Also, from Wikipedia:

    The most direct competitor of quicksort is heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always Θ(nlogn). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant, which switches to heapsort when a bad case is detected. If it is known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it.