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