Hi Herman,
HS>HS> 1) With an already sorted list fast bubble sorts executes fastest
HS>GW>But with a nearly sorted list I would expect insertion sort to be
HS>GW>fastest (what is the point of running a sort routine against data one
HS>GW>already knows is ordered?)
HS>Not necessarily completely sorted. If you have minor
HS>disordered elements then bubble sort would be the fastest.
I've run a load of tests, and as far as I'm concerned Insertion sort is
never slower then bubble sort with the early exit test, and usually
faster. A typical set of results follows where:
Rand uses a standard set of data generated at the start of the run
Sort uses the sorted version of Rand
Srt1 uses the sorted data with an element 10% from the start set to
     the replacement value
Srt2 uses the sorted data with an element 10% from the end set to
     the replacement value
"bubble" is the classic bubble sort algorithm
"Quick Bubble" is "bubble" with early exit if no exchanges in a pass
"Insertion" is the standard insertion sort as posted by David Noon.
Blank fields are where testing was supressed because it took too long
to run.
Tests for short integer data normalised to 1000 repeats in clock() ticks.
Data Range    11 to 32738
Replacement value for srt1 & srt2 is 11
Set Size    bubble      |   Quick Bubble    |    Insertion
     Rand Sort Srt1 Srt2 Rand Sort Srt1 Srt2 Rand Sort Srt1 Srt2
4000                             6                  10   11   19
2000                             2                   4    5    9
1000                             1                   2    2    4
 500                             0   36  187  133    0    0    2
 250   82   46   46   47   87    0    8   46   33    0    0    0
 125   20   11   11   11   21    0    2   11    8    0    0    0
  62    4    2    2    2    5    0    0    2    2    0    0    0
  31    0    0    0    0    0    0    0    0    0    0    0    0
Replacement value for srt1 & srt2 is 16374
Set Size    bubble      |   Quick Bubble    |    Insertion
     Rand Sort Srt1 Srt2 Rand Sort Srt1 Srt2 Rand Sort Srt1 Srt2
4000                             6   15             10   15   14
2000                             2    7              4    7    6
1000                             1    3              2    3    3
 500                             0    1  122  133    0    1    1
 250   82   46   46   46   87    0    0   30   33    0    0    0
 125   20   11   11   11   21    0    0    6    8    0    0    0
  62    4    2    2    2    5    0    0    1    2    0    0    0
  31    0    0    0    0    0    0    0    0    0    0    0    0
Replacement value for srt1 & srt2 is 32738
Set Siz     bubble      |   Quick Bubble    |    Insertion
     Rand Sort Srt1 Srt2 Rand Sort Srt1 Srt2 Rand Sort Srt1 Srt2
4000                             6   21   12        10   21   11
2000                             2   10    6         4   10    5
1000                             1    4    2         2    4    2
 500                             0    2    1  133    0    2    1
 250   82   46   46   46   87    0    0    0   33    0    0    0
 125   20   11   11   11   21    0    0    0    8    0    0    0
  62    4    2    2    2    5    0    0    0    2    0    0    0
  31    0    0    0    0    0    0    0    0    0    0    0    0
HS>GW>Have you investigated the Quickersort variation: useing insertion
HS>GW>sort when the partition to be sorted is less than a set number of
HS>GW>elements (7 is a typical value), and also Singletons method of 
electing
HS>GW>the key as the median of the left, right, and centre values of the
HS>GW>partition.
HS>No I haven't. Post some code.
I'm working on it, I've got some sample code done, but not all I wanted.
I Will post when polishing/testing complete. But during my tests I
noticed that the end of your quick sort code, below, needs changing as
indicated, otherwise you never sort the first partition put on the stack
:-(.
               if (p != 0)
               {
                    l = sl[p][0];
                    r = sl[p][1];
                    p--;
               }
                        else            /* ADD */
                           break;       /* ADD */
          }
/*     while(p > 0);    CHANGE TO */
       while (1);
     }
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------