// Program to read a  list of numbers, sort them using the Insertion Sort 
// algorithm, and  print the numbers in sorted order

#include <iostream>

using namespace std;

const int SENTINEL = -999;
const int MAXSIZE = 100;

int main()
{
   	int A[MAXSIZE];  // declare an array A of integers of 100 elements 

	             // we will study later on dynamic memory allocation, i.e., how 
	             // to declare an array whose size is specified during run time
    


	// read a list of number and store them in an array 
	int i;
	cout << "Enter a list of numbers ending with " << SENTINEL << endl;		
	int number;
	cin >> number;
	i = 0;
	while (number != SENTINEL  )						
	{ 						   								
		A[i] = number;
	    i++;
	    cin >> number;
	}
    int n = i; // the number of elements in the array

    ////////////////////////////////////////////////////////
    ////////////// Insertion Sort //////////////////////////
    ////////////////////////////////////////////////////////
	for(int j=1;j<n;j++) 
	{
        int key = A[j];
        // Insert A[j] into the sorted sequence  A[0���j-1]
        i = j-1;
        while(i>=0 && A[i] > key) 
		{ 
              A[i+1] = A[i];  // move the elements ahead
              i =i-1;          // and go one step back
		}
        A[i+1] = key;
    }
    ////////////////////////////////////////////////////////
	 ////////////////////////////////////////////////////////

	//Print numbers in sorted order
    cout << "The numbers in sorted order are:"<<endl;
	for (i = 0; i< n; i++)
		cout << A[i] << " ";

	cout << endl;

	return 0;
}