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
+ 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
1 Reply

 P: n/a In article <11*********************@z14g2000cwz.googlegroups. com>, Matt Bitten wrote:Can someone tell me why Musser's Introsort algorithm switchesto Heapsort when the recursion depth of Quicksort gets toolarge. Wouldn't Mergesort be a better choice? It's fasterthan Heapsort, isn't it? I know Mergesort does not work inO(1) additional space, the way Heapsort does, but neitherdoes 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 beany "comp.algorithms" group ... or anything of a similarnature.) 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.