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

Re: Wording of the rationale



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/