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

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.

*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):