// File: Sorting/insort.C
// Insertion sort (see Sedgewick, p. 98)
// Programmer: E. Kaltofen (September 21, 1992)
typedef int itemType; // for testing purposes

int insort(itemType A[], int n)
// sorts the array A[0],...,A[n-1] into < order
// does not need a guard at A[-1]
// note: one must have itemType operator<(itemType)
// returns the number of comparisions
{int i, j, comp = 0;
 itemType a0; // save first element
 if(n < 1) return(-1); // indicates erroneous argument n
 if(n == 1) return(comp);
 a0 = A[0];
 if(n == 2) {comp++;
             if(A[1] < a0)
               {A[0] = A[1]; A[1] = a0;};
             return(comp);};

 // insert A[2] correctly into A[1]; saves 1 comparison in the loop later 
 comp++;
 if(A[2] < A[1])
   {A[0] = A[2]; A[2] = A[1]; A[1] = A[0];};

 for(i=3; i<=n-1; i++)
    {// the array segment A[1],...,A[i-1] is in order
     // now we insert A[i]
     comp++;
     if(A[i] < A[i-1])
       {// something has to be shifted
        A[0] = A[i]; // save element to be inserted
                     // and use as sentinel at the same time
        // shift first larger element right
        A[i] = A[i-1];
        j = i-2; comp++;
        // innermost loop, as efficient as possible
        while(A[0] < A[j])
             {A[j+1] = A[j]; // shift element larger than A[i] to right
              j--; comp++;};
        // A[j] <= A[i] and A[j+1] is vacated for A[i] (stored in A[0])
        A[j+1] = A[0]; }; };
 // insert the first element
 comp++;
 if(A[n-1] < a0)
   {// a0 goes into A[n-1], shift everything over
    for(j = 0; j < n-1; j++) A[j] = A[j+1]; // shift smaller elements to left
    A[n-1] = a0;}
  else
    {// find place for a0
     j = 1; comp++;
     while(A[j] < a0) // note: this condition fails for j==n-1
          {A[j-1] = A[j]; // shift smaller elements to left
           j++; comp++;};
     // A[j] >= a0 and A[j-1] is vacated for a0
     A[j-1] = a0;}
 return(comp);}// end insort