[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.

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