// File Sorting/indir_insort.C
// Indirect insertion sort (see Sedgewick, p. 104)
// Programmer: E. Kaltofen (September 23, 1992)
// Modified by: Mohan Nibhanupudi (September 21,1994)
//              (removed case n==2)
#include <iostream.h>

typedef int ElType; // for testing purposes

int indir_insort(ElType A[], int n, int I[])
// set the array I[0],...,I[n-1] such that 
// A[I[0]] < A[I[1]] < ... < A[I[n-1]]
// note: one must have ElType operator<(ElType)
// returns the number of comparisons
{int i,j,comp=0;
 if(n < 1) {cerr << "Can't indirectly sort 0 or less elements" << endl;
            return(-1);}

 if(n == 1) {I[0] = 0; return(0);};

 // "sort" I by using the comparision I[i] "<" I[j] if A[I[i]] "<" A[I[j]]
 I[1] = 1;
 for(i=2; i<=n-1; i++)
    {// the array segment A[I[1]],...,A[I[i-1]] is in order,
     // and I[1],...,I[i-1] is a permutation of 1...i-1
     // now we insert index i
     comp++;
     if(A[i] < A[ I[i-1] ])
       {// something has to be shifted
        I[0] = i; // save index of element to be inserted
                  // and use as sentinel at the same time
        // shift first larger element right
        I[i] = I[i-1];
        j = i-2; comp++;
        // innermost loop, as efficient as possible
        while(A[ i ] < A[ I[j] ])
             {I[j+1] = I[j]; // shift index of element larger than A[i] to right
              j--; comp++;};
        // A[ I[j] ] <= A[ I[i] ] and I[j+1] is vacated for i
        I[j+1] = i;}
     else I[i] = i;
     };
 // insert the first element
 comp++;
 if(A[ I[n-1] ] < A[0])
   {// A[0] is largest element
    for(j = 0; j < n-1; j++) I[j] = I[j+1]; // shift smaller elements to left
    I[n-1] = 0;}
  else
    {// find the place of A[0]
     j = 1; comp++;
     while(A[ I[j] ] < A[0]) // note: this condition fails for j==n-1
          {I[j-1] = I[j]; // shift smaller elements to left
           j++; comp++;};
     // A[0] is in j-1 place
     I[j-1] = 0;}
 return(comp);}// end indir_insort