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.

Improve this question
$\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 10:40

1 Answer 1

Reset to default
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)

Improve this answer
$\endgroup$
5
  • $\begingroup$ But heapsort is used... and I suspect it's because it's in place like quicksort. $\endgroup$
    – user672009
    May 6, 2014 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$
    – Wandering Logic
    May 6, 2014 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$
    – Wandering Logic
    May 6, 2014 at 14:46
  • $\begingroup$ Additionally, heapsort has many more cache misses than introsort. $\endgroup$
    – noɥʇʎԀʎzɐɹƆ
    Jul 26, 2017 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, 2017 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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