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
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