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

*To*: Aubrey Jaffer <agj@alum.mit.edu>*Subject*: Re: Wording of the rationale*From*: Per Bothner <per@bothner.com>*Date*: Sun, 12 Nov 2006 16:06:59 -0800*Cc*: srfi-95@srfi.schemers.org*Delivered-to*: srfi-95@srfi.schemers.org*In-reply-to*: <20061112234042.E84F051D732@home.voluntocracy.org>*References*: <455080C2.2090103@soegaard.net> <20061112234042.E84F051D732@home.voluntocracy.org>*User-agent*: Thunderbird 1.5.0.8 (X11/20061107)

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/

**Follow-Ups**:**Re: Wording of the rationale***From:*Aubrey Jaffer <agj@alum.mit.edu>

**References**:**Wording of the rationale***From:*Jens Axel Søgaard <jensaxel@soegaard.net>

**Re: Wording of the rationale***From:*Aubrey Jaffer <agj@alum.mit.edu>

- Prev by Date:
**Re: Memory use of sort!** - Next by Date:
**Re: Memory use of sort!** - Previous by thread:
**Re: Wording of the rationale** - Next by thread:
**Re: Wording of the rationale** - Index(es):