gotchaMinor
Why does introsort use heapsort rather than mergesort?
Viewed 0 times
whymergesortintrosortthanratherheapsortdoesuse
Problem
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.
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.
Solution
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)
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)
Context
StackExchange Computer Science Q#24446, answer score: 9
Revisions (0)
No revisions yet.