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

Re: Wording of the rationale

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
	--Per Bothner
per@bothner.com   http://per.bothner.com/