# Why does introsort use heapsort rather than mergesort?

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.

• If introsort is part of the question, you'll have to tell us what it is before we can say anything. – Louis May 6 '14 at 9:30
• 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. – FrankW May 6 '14 at 9:41
• 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. – user672009 May 6 '14 at 9:52
• @user672009 In that case, write down code for either and see what you find. The reason may or may not be related to performance. – Raphael May 6 '14 at 10:29
• I have concluded that since quicksort sorts in place we need to use another in place sorting algorithm. However I'm open for input. – user672009 May 6 '14 at 10:40

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)

• But heapsort is used... and I suspect it's because it's in place like quicksort. – user672009 May 6 '14 at 11:18
• 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. – Wandering Logic May 6 '14 at 14:45
• @user672009, $O(1)$ space means "in place," and quicksort is not quite in place because it requires $O(\lg n)$ extra space. – Wandering Logic May 6 '14 at 14:46
• Additionally, heapsort has many more cache misses than introsort. – noɥʇʎԀʎzɐɹƆ Jul 26 '17 at 19:29
• 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. – gnasher729 Jul 27 '17 at 9:55