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