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

*To*: Jens Axel Søgaard <jensaxel@soegaard.net>*Subject*: Re: Wording of the rationale*From*: Per Bothner <per@bothner.com>*Date*: Tue, 07 Nov 2006 18:53:05 -0800*Cc*: srfi-95@srfi.schemers.org*Delivered-to*: srfi-95@srfi.schemers.org*In-reply-to*: <455080C2.2090103@soegaard.net>*References*: <455080C2.2090103@soegaard.net>*User-agent*: Thunderbird 1.5.0.7 (X11/20061027)

Jens Axel Søgaard wrote:

* Four varieties of algorithms were provided (quick, heap, insert, merge) even though quick, heap, and insert sorts have no significant advantage over merge-sort. ... Second: What does "no significant advantage" mean? I were of the impression, that the "hidden constants" of O(n log (n)) of vector-quick-sort were smaller than that of vector-merge-sort.

My impression is that is non-trivially faster when you're sorting an array of integers, with no indirection through a "compare" function. In practice, one (almost) never sorts an array of integers (one sorts an array of records/objects - which may have integer fields), and one usually indirects though a compare function. That changes the "constant factors" significantly. It is illustrative that java.util.Arrays uses a "tuned quicksort" for sorting arrays of "primitive" (unboxed) numbers, but a "modified mergesort" to sort Object arrays. > Also: Is merge-sort the fastest algorithm, if the elements are "almost > sorted"? From the Java documentation: This [modified merge-sort] algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists. -- --Per Bothner per@bothner.com http://per.bothner.com/

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

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