[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Wording of the rationale



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/