heap and insertion sorts

[Sean Kelly]

David Medlock wrote:
> 
> Ported from public domain code.
> 
> 
> // =====================================
> // insertion sort
> // =====================================
> template isort(T)
> {
>   void isort(T[] array, int delegate(T,T) compare = null)
>   {
>     int cmp( T x, T y ) { return x<y ? -1 : x==y ? 0 : 1 ;}
> 
>     if ( compare is null ) compare = &cmp;
> 
>     // shift elements until this value can be inserted
>     void reinsert( T value, int start )
>     {
>       while( start >=0 )
>       {
>         if ( cmp(array[start], value) < 0 ) break;

This should be 'compare'.

>         array[start+1]=array[start];
>         start--;
>       }
>       array[start+1] = value;
>     }
> 
>     for (int i = 1; i < array.length; i++)
>     {
>       if ( cmp(array[i-1],array[i])>0 )  reinsert( array[i] , i-1 );

This too.

>     }
>   }
> }


Sean