Introsort

[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

[Dave Vandervies]

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