// ----- Example:  Insertion Sort ---
//
// This program reads in an integer array of user-specified 
// length and sorts its entries. The 
// elements in the array are then printed in sorted order.
// Dynamic memory allocation is used so that the array
// is always just the right length.
// -----------------------------------------------
#include<iostream>
using namespace std;

// -----------------------------------------------
void insert_sort( int* , int* , int  );
void insert( int , int* , int , int spot);
// -----------------------------------------------

int main()
{
   int i, n;
   cout << "\n Enter the length of the integer array: ";
   cin  >> n;
   int *a     = new int [n]; // Dynamic memory allocation
   int *b     = new int [n]; // Dynamic memory allocation

// -----------------------------------------------
//  Get the first array.
// -----------------------------------------------
   cout << "\n Enter the elements of the integer array one by one:  \n\n";
   for (i = 0; i < n; ++i)
   {
    cout << "enter a[" << i << "]:  ";
    cin >> *(a+i);
   }

   insert_sort( a, b, n );

// -----------------------------------------------
//  Print out the sorted array:
// -----------------------------------------------
   cout << " \n The sorted array is: \n\n";
   i=0;
   while ( i < n ) 
     {
       cout <<   *(b+i) << "  ";
       ++i;
     }
   cout << "\n\n";
// -----------------------------------------------
//  Return the dynamic memory to the heap:
// -----------------------------------------------
   delete [] a;
   delete [] b;

   return 0;
} 


void insert_sort( int* a, int* b, int length )
{
   int i, j, found;
   for ( i = 0; i < length; ++i )
   {
     j = 0; 
     while( j < i )              // Remark: a for() loop here 
     {                           // increments j one extra time!
       if ( *(a+i) < *(b+j) )
          break;
       ++j;
     }
     insert( a[i], b, i, j);
   }
}


void insert( int value, int* b, int length, int spot)
{
   int i = length;
   while (i > spot)
   {
     *(b+i) = *(b+i-1);
      i--;
   }
   *(b + spot) = value;
}