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$
  • 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$
  • $\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$ – Wandering Logic 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$ – Wandering Logic May 6 '14 at 14:46
  • $\begingroup$ Additionally, heapsort has many more cache misses than introsort. $\endgroup$ – noɥʇʎԀʎzɐɹƆ 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.