Hi David;
You wrote to Roger Scudder:
DN>[snip]
DN>RS> Quick sort isn't what?   Do you mean fast?  I was under the
DN>RS> impression that it was fast.
DN>Mileage varies with Quicksort. However, qsort() is usually quite a deal
DN>slower than a well-crafted custom sort.
For in memory sorting Quicksort with all the tweaks comes out fastest
overall in my testing on anything but close to ordered data, when
insertion sort takes the prize. No change from when I first tracked it
down (by reading CACM) all those years ago at University (only vol 1 of
Knuths books was published then and Vol 3 was some years in the
future!). I've still got the (off topic) Algol 60 source around
somewhere :-)
DN>RS> This is an interesting thread.
DN>Yes, isn't it?  It might be more on-topic, too, if somebody other than
DN>Herman Schonfeld and me posted code.
........................^^
???? Language! :-) Surely you mean "and I" :-)
You have your wish :-). See implementation of "Straight Selection" sort
in message to Tom Torfs in this upload :-)
We'll have to have a go at heapsort soon. According to Knuth it's the
only one guaranteed to be of order N log N, but his analysis is that it
will always be slower than quicksort on average, and only beat shellsort
for very large N.
I like Knuth's quote on page 180 of Vol 3, it seems most appropriate to
these threads on sorting:-
"As soon as an Analytical Engine exists, it will necessarily guide the
future course of the science. Whenever any result is sought by its aid,
the question will then arise - By what course of action can these
results be arrived at by the machine in the shortest time?"
Babbage (1864)
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------