Hi David,
You wrote to me:
DN>DN>Neither would I. I would not use them for more than 8.
DN>GW>Seconded (though maybe I'd go up to 10 items).
DN>Mileage varies with the type of data being sorted and the suitability of 
the
DN>CPU used. For character strings on an Intel I would stick with 8, but
DN>doubles, as I used above, would likely be Ok up to 10.
'tis interesting. I've been playing on that aspect too :-)
For the full standard library qsort() replacements (that use external
compare routines and are passed data item length) the switch point is
7 elements.
For a routine optimised for char data it was fairly high - I saw
improvements in sort time up to 40, but I suspect it is sensitive to
total sort length.
For short data 13 to 18 gave the same time - so probably 15 would be
optimum.
For long data 9 to 11 gave the same time - so 10 is optimum in that
case.
DN>GW>My test timings were instructive. With all the speed ups a quickersort
DN>GW>is faster than shellsort except where the data is close to ordered, and
DN>GW>even then it isn't too far behind. Your code as posted in the template
DN>GW>in C_Plusplus would be very slow on close to ordered data because the
DN>GW>test key you use brings it back to N^2 time.
DN>Yes, that's a known defect in Hoare's algorithm. It prefers a mess to 
almost
DN>ordered data.
But he recognised it and suggested improvements.
DN>GW>Using R. C. Singleton's
DN>GW>method of selecting the median of the left, right and center elements 
s
DN>GW>test key improves peformance significantly in this case (and improves 
t
DN>GW>in general as well ).
DN>Watch C_PlusPlus for a new template soon.
:-)
I'll put the fully optimised code for integral types I'm working up
from the general qsort() in SNIPPETS up locally (or do you want to
discuss this and play with ideas on Saturday?). I think it may provide a
good basis for a template...
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------