Sort the elements of an array A in ascending order.

Method: Every repetition of insertion sort, removes an element from the input data, inserts it into the correct position in the already sorted list until no input elements remain.

Sorting is typically done in-place.

A:    <=x  |   >x  |    x   |  ...
    partially sorted   unsorted 
insert x in the partially sorted array

A:    <=x  | x  |   >x  |      ...
         partially sorted     unsorted 
Repeat untill the unsorted part is within the sorted part

#include<stdio.h>
#include<conio.h>
#define SIZE 50
void main()
{
	int A[SIZE], N;
	int i, j, v;

	do {
		printf("Enter the dimension: ");
		scanf("%d", &N);
	} while (N <= 0 || N > SIZE);

	for (i = 0; i < N; i++)
	{
		printf("Enter A[%d]: ", i);
		scanf("%d", &A[i]);
	}

 	/* Insertion Sort  */
	// the first element A[0] is the sorted part of the array
	// begin from second element and inserted it in the sorted array (behind its position)
  	for (i = 1; i <  N; i++)
  	{
  		v =  A[i];  // v will be placed in the sorted array
  		j = i;
  
  		while (j > 0 && A[j-1] >v)	//we move backward in the sorted array till we found the place
  		{
  			A[j] = A[j-1];
  			j--;
  		}
  		A[j] =  v;			// put v in the j index
  	}

	printf("\n\n** After sorting ** \n");
	for (i = 0; i < N; i++)
	{
		printf("A[%d]=%d\n", i, A[i]);
	}

	getch();
}