(Previous discussion continued) | ||
Re: Wording of the rationale | Per Bothner | 13 Nov 2006 00:06 UTC |
Re: Wording of the rationale Per Bothner 13 Nov 2006 00:06 UTC
Aubrey Jaffer wrote: > http://en.wikipedia.org/wiki/Sorting_algorithm has a table of > properties for sort algorithms. "In-place merge sort" is shown as > stable, O(n log(n)) time, and using no additional memory. "In-place merge sort" works well for lists. Is there an in-place version for vectors? On the other hand, to kill those claims that quicksort is "quick": In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case; merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case. [Same wikipedia link] So basically Quicksort wins when comparisons are cheap and copying is expensive. For example when each move means copying a large record. Of course nobody does that, especially not in Scheme/Lisp: when you're sorting a list/vector of records, you move pointers, not the records themselves. -- --Per Bothner xxxxxx@bothner.com http://per.bothner.com/