Hi Herman,
HS>I've been seeing endless threads of "best sort algorithm", and similarly,
HS>identical questions being asked over and over again. I have decided to 
est
HS>every sort algorithm in question thus yielding the "best sort algorithm"
HS>so many people desire.
HS>Theory has it that the performance of a sorting algorithm is dependant
HS>upon
HS> a) the number of items to be sorted and
HS> b) how unsorted the list is to start with.
HS>With this in mind it is worth testing the various sorting routines
HS>described here to determine which one will best suit your particular
HS>application. Here are some basic rules for chosing which type of sort
HS>alogorithm would best suit your specific problem :-
HS> 1) With an already sorted list fast bubble sorts executes fastest
But with a nearly sorted list I would expect insertion sort to be
fastest (what is the point of running a sort routine against data one
already knows is ordered?)
HS> 2) With a random list of small variations between the values a
HS>     shell sort would execute fastest
HS> 3) With a random list of large variations between the values
HS>     quicksort executes the fastest
HS>When considering a sort routine take into consideration memory
HS>constraints and the type of data to be sorted as well as the relative
HS>performances of the sort functions. Generally, the faster a sort
HS>operates, the more memory it requires. Compare a simple bubble sort
HS>with the quick sort, and you will see that the quick sort requires far
HS>more memory than the bubble sort.
Now there is something most people don't consider. There is no "best"
sort!
HS>Some code to demonstrate follows.
You have used the classic Quicksort with an internal stack (and an
enormous one at that!), but without putting the _largest_ of the two
partitions on the stack (which the classic algorithm specifies). If the
largest partition is put on the stack Quicksort has a stack use of
lg(N+1)/(M+2), where N is the number of elements and M is the length of
the arrays when recursion is stopped and another sort (usually
insertion) used for the final phase.
A stack 100 deep will allow sorting of arrays of up to around 10**43!!!
With a 20 deep stack the limit is around 10**8.
This makes the memory use of quicksort much more reasonable.
Have you investigated the Quickersort variation: useing insertion
sort when the partition to be sorted is less than a set number of
elements (7 is a typical value), and also Singletons method of selecting
the key as the median of the left, right, and centre values of the
partition.
From my testing they allow quickersort to keep up with shellsort under
nearly all circumstances.
A comprehensive examination, congratulations!
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------