By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,778 Members | 1,919 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,778 IT Pros & Developers. It's quick & easy.

Introsort

P: n/a
Can someone tell me why Musser's Introsort algorithm switches
to Heapsort when the recursion depth of Quicksort gets too
large. Wouldn't Mergesort be a better choice? It's faster
than Heapsort, isn't it? I know Mergesort does not work in
O(1) additional space, the way Heapsort does, but neither
does Quicksort, so we don't seem to be gaining anything.

(Yeah, this isn't about C++, but there doesn't seem to be
any "comp.algorithms" group ... or anything of a similar
nature.)

-- Matt

Jul 23 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
In article <11*********************@z14g2000cwz.googlegroups. com>,
Matt Bitten <mb*******@yahoo.com> wrote:
Can someone tell me why Musser's Introsort algorithm switches
to Heapsort when the recursion depth of Quicksort gets too
large. Wouldn't Mergesort be a better choice? It's faster
than Heapsort, isn't it? I know Mergesort does not work in
O(1) additional space, the way Heapsort does, but neither
does Quicksort, so we don't seem to be gaining anything.
Mergesort requires O(n) space for a copy of the data, which can get
expensive for large amounts of data or large data items. Quicksort-
with-depth-limit only requires O(lg n) additional space, and only for
index values, with no additional space required for a copy of the data.
Anything that can sort in-place (with or without space requirements
for activation records) tends to be a pretty big win space-wise over
algorithms that require working space for a copy of the data.

(Yeah, this isn't about C++, but there doesn't seem to be
any "comp.algorithms" group ... or anything of a similar
nature.)


comp.programming is a good place to discuss the practical implications
of algorithms. Crossposted and followups set.
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca

Your assertion is noted. I disagree entirely with it.
--Richard Heathfield in comp.lang.c
Jul 23 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.