Hi David,
You wrote to me:
DN>DN>Mileage varies with Quicksort. However, qsort() is usually quite a deal
DN>DN>slower than a well-crafted custom sort.
DN>GW>For in memory sorting Quicksort with all the tweaks comes out fastest
DN>GW>overall in my testing on anything but close to ordered data, when
DN>GW>insertion sort takes the prize.
DN>Insertion sort is faster than Shellsort?  I have to express some 
kepticism
DN>about that, or did you exclude Shellsort from your tests?
Yes. It depends on the amount of disturbance to the data set (the
crossover point for data set size varies in inverse proportionality to
the amount of disturbance), but for small disturbance (<2.5% elements
displaced @ 250 elements) it is faster. I've tested shellsort (ssort()
in SNIPPETS) against the fully tweaked quickersort (qsort() from
SNIPPETS) and both have similar timings on already ordered data.
I need to do more work on my test harness before I post it. I know of
some structural changes to make it postable, there is some poor codeing
practise in there (but it's OK for the "quick & dirty" testing things
out code it started out as).
DN>I have already coded a template for that algorithm and will be posting it 
in
DN>C_PlusPlus in the next installment, probably tomorrow night.
:-)
DN>GW>We'll have to have a go at heapsort soon. According to Knuth it's the
DN>GW>only one guaranteed to be of order N log N, but his analysis is that it
DN>GW>will always be slower than quicksort on average, and only beat 
hellsort
DN>GW>for very large N.
DN>Are you reading my hard drive while I'm at work?
Nope. Just looking at all the options :-)
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------