Hi Jasen,
You wrote to David Noon:
JB>DN> JB>Also your insertion sort could use a bisection search to find the
JB>DN> JB>insertion place and memmove to do the move of multiple items to 
ake
JB>DN> JB>room to insert, this would speed it up considerably (I'm expecting
JB>DN> JB>2-3 times)
JB>DN> Bisection searching?
JB>DN>
JB>DN> This usually presupposes sorted data. Please post some code to show us
JB>DN> how you do it.
JB>When you are insertion sorting, you pick the next item off the unsorted 
nd
JB>the array and insert it into the sorted end. (I probably
JB>could stop right here)
:-)
JB>The sorted end is by nature sorted :), so it can be bisection searched to 
fi
JB>the insertion position.
It is a helpful technique when data is added to the end of an already
sorted data set, especially if the early exit technique at "note above"
is used to rapidly skip already sorted data. If there is only a relatively
small amount of extra data it is, in my testing, the quickest sort.
On random data, unless you are maintaining a sort order on another key,
there are better routines (as you've already found and reported)
although it does help speed things up on larger data sets, on small
data sets (which is all insertion sort is usually suitable for) the time
overhead of implemeting the bi-section search is more than the time it
saves.
JB>some code: (which still needs a little tidying up)
:-).
JB>void newINSERTION()
JB>     {
JB>          int top;
JB>          int a,b,c;
JB>          char temp[20];
JB>          for(top=0; top < lastone; top++)
JB>          {
JB>               strcpy(temp,data[top + 1]);
JB>   /* Bisection search */
JB>               a=0,b=top+1;
JB>               while(a!=b)
JB>                 if( strcmp(data[c=(b+a)/2],temp) <0)
JB>                  a=c+1; else b=c;
JB>    /* Insert */
JB>               memmove(data+a+1,data+a,(1+top-a)*sizeof(data[0]));
JB>               strcpy(data[b],temp);
JB>          }
JB>     }
Some code to keep David happy (it's based on his to save typing anyway ).
Ascending sort with memmove & bisection search
#define TYPE short
void ascending (TYPE array[], int n)
{
int i,left,right,split;
TYPE Hold_it_here;
for (i = 1; i < n; ++i)
    {
    if (array[i] < array[i-1])  /* Note above */
        {
        Hold_it_here = array[i];
        left = 0;
        right = i;
        while (left != right)
            {
            if (Hold_it_here > array[(split = (right + left)/2)])
                left  = split + 1;
            else
                right = split;
            }
        if (left != i)
            {
            memmove (&array[left + 1],&array[left],(i-left) * sizeof 
(array[0])
            array[left] = Hold_it_here;
            }
        }
    }
return;
}
Timings...
I've done a lot of testing and can't find any suitable timings to present.
All I can deduce from my testing is that it is generally slower than the
standard sorts given the same test data and customisation, but in the
specific case I referred to above of a small amount of new data added to the
end of an already sorted data set it can be the fastest sort. I could draw
no generalisations as to data set size or amount of extra data where it had
an advantage, although the smaller the amount of new data the larger
the data set size where it was fastest, so for those following the
thread its a case of test it yourself for your specific requirements...
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------