9
$\begingroup$

As part of a homework assignment covering implementation of introsort I'm asked why heapsort is used rather than mergesort (or other $O(n\log(n))$ algorithms for that matter).

Introsort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. (Wikipedia, retrieved 2014-May-06.)

The only reason I can think of is that heapsort is "in place" ... But tbh I don't really understand why this would matter here though.

$\endgroup$
6
  • 3
    $\begingroup$ If introsort is part of the question, you'll have to tell us what it is before we can say anything. $\endgroup$
    – Louis
    May 6 '14 at 9:30
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – FrankW
    May 6 '14 at 9:41
  • $\begingroup$ We are simply asked to make some pseudo code for intro sort and later on we are asked why it uses heapsort rather than mergesort. $\endgroup$
    – user672009
    May 6 '14 at 9:52
  • $\begingroup$ @user672009 In that case, write down code for either and see what you find. The reason may or may not be related to performance. $\endgroup$
    – Raphael
    May 6 '14 at 10:29
  • 2
    $\begingroup$ I have concluded that since quicksort sorts in place we need to use another in place sorting algorithm. However I'm open for input. $\endgroup$
    – user672009
    May 6 '14 at 10:40
9
$\begingroup$

The 2 downsides of quicksort is that it requires $O(\log n)$ extra space (to keep the unsorted intervals) and bad pivot selection (or contrived sequences designed to make you select a bad pivot) may cause it to be a $O(n^2)$ time and $O(n)$ extra space algorithm.

Switching to heapsort when the recursion depth becomes too large (at around $\log n$) means we have a guaranteed upperbound that is $O(n \log n )$ time and $O( \log n)$ extra space.

Heapsort's $O(1)$ extra space requirement makes it a better choice to mergsort's $O(n)$ where for a contrived array that $n$ could still be large.

The reason heapsort isn't used for the full sort is because it is slower than quicksort (due in part to the hidden constants in the big O expression and in part to the cache behavior)

$\endgroup$
5
  • $\begingroup$ But heapsort is used... and I suspect it's because it's in place like quicksort. $\endgroup$
    – user672009
    May 6 '14 at 11:18
  • $\begingroup$ I suspect that @user672009 is confused by your last sentence. I'd suggest clarifying that introsort doesn't start with heapsort because it is slower. $\endgroup$ May 6 '14 at 14:45
  • $\begingroup$ @user672009, $O(1)$ space means "in place," and quicksort is not quite in place because it requires $O(\lg n)$ extra space. $\endgroup$ May 6 '14 at 14:46
  • $\begingroup$ Additionally, heapsort has many more cache misses than introsort. $\endgroup$ Jul 26 '17 at 19:29
  • $\begingroup$ A good Quicksort implementation doesn't need O (n) space in the worst case, as long as it remembers the larger subinterval on the stack, and handles the smaller immediately. $\endgroup$
    – gnasher729
    Jul 27 '17 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.