Introsort

M

Matt Bitten

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
 
D

Dave Vandervies

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top