heap and insertion sorts

[David Medlock]

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;
         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 );
     }
   }
}



// =====================================
// Heapsort
// =====================================
template hsort(T)
{
   void hsort( T[] array, int delegate(T,T) compare = null )
   {
     int cmp( T a, T b ) { return a<b ? -1 : a==b ? 0 : 1;}
     if ( compare is null ) compare = &cmp;

     int parent( int n ) { return (n&1)==0 ? (n/2)-1 : (n/2); }
     int left( int n)    { return n*2 + 1; }
     int right( int n )  { return n*2 + 2; }

     void swap( int a, int b )
     {
       T temp = array[a];
       array[a] = array[b];
       array[b] = temp;
     }

     int heapsize = array.length -1 ;

     void heapify( T[] array, int which )
     {
       int L = left(which);
       int R = right(which);
       int large = which;
       if ( L < heapsize ) if ( compare(array[L] ,array[which] ) > 0 )
       {
          large = L;
       }

       if ( L < heapsize ) if ( compare(array[R] ,array[large] ) > 0 )
       {
          large = R;
       }
       if ( large != which )
       {
         swap( large, which );
         heapify( array, large );
       }
     }

     for (int i = (heapsize-1) / 2; i >= 0; i--)
     {
       heapify(array, i);
     }

     for (int i = heapsize; i > 0; i--)
     {
       swap( 0, heapsize );
       heapsize--;
       heapify(array, 0);
     }
   }
}