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/