This page is part of the web mail archives of SRFI 95 from before July 7th, 2015. The new archives for SRFI 95 contain all messages, not just those from before July 7th, 2015.
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 per@bothner.com http://per.bothner.com/