In a message dated 04-06-98, George White said to David Noon about Faster
Than A Snail On .
Hi George,
DN>Mileage varies with Quicksort. However, qsort() is usually quite a deal
DN>slower than a well-crafted custom sort.
GW>For in memory sorting Quicksort with all the tweaks comes out fastest
GW>overall in my testing on anything but close to ordered data, when
GW>insertion sort takes the prize.
Insertion sort is faster than Shellsort?  I have to express some skepticism
about that, or did you exclude Shellsort from your tests?
DN>Yes, isn't it?  It might be more on-topic, too, if somebody other than
DN>Herman Schonfeld and me posted code.
GW>.....................^^
GW>???? Language! :-) Surely you mean "and I" :-)
[Switching from C to English]
No. I think the pronoun is in the dative case in that context.
[Back to C, sort of]
GW>You have your wish :-). See implementation of "Straight Selection" sort
GW>in message to Tom Torfs in this upload :-)
At last. ... :-)
I have already coded a template for that algorithm and will be posting it in
C_PlusPlus in the next installment, probably tomorrow night.
GW>We'll have to have a go at heapsort soon. According to Knuth it's the
GW>only one guaranteed to be of order N log N, but his analysis is that it
GW>will always be slower than quicksort on average, and only beat shellsort
GW>for very large N.
Are you reading my hard drive while I'm at work?
GW>I like Knuth's quote on page 180 of Vol 3, it seems most appropriate to
GW>these threads on sorting:-
GW>"As soon as an Analytical Engine exists, it will necessarily guide the
GW>future course of the science. Whenever any result is sought by its aid,
GW>the question will then arise - By what course of action can these
GW>results be arrived at by the machine in the shortest time?"
GW>Babbage (1864)
It is painfully obvious that nobody at Microsoft has ever read that quote.
We should send it to them, compliments of this echo. [Or better yet, the
80XXX echo.]
Regards
Dave

___
 * MR/2 2.25 #353 * Always ready to pervert pure science for a fast buck!
--- Maximus/2 3.01
---------------