How does insertion sort work

Insertion sort is also a comparison based sorting. It is also an in-place sorting algorithm i.e it does not require extra space. We can re-arrange the elements within the array itself.The algorithm works as follows.

The array is divided into two parts one sorted and one un-sorted. Initially the sorted part will be empty and the unsorted part will be the entire array. We assume that the first element is sorted and start with the second element. we will insert that into the correct place in the sorted part. The same procedure is repeated for the remaining elements also until the entire array is sorted. In each iteration, when a new element is to be inserted into the sorted array, we need to shift the greater elements one step right to make space.

For example let us consider a simple array [3,1,5,2,4]. Following is the state of the array in each iteration. I have divided the array in two parts for convenience.

Step   |Sorted    | Unsorted
—————————–
1:     [3]        | [1,5,2,4]
2:     [1,3]      | [5,2,4]
3:     [1,3,5]    | [2,4]
4:     [1,2,3,5]  | [4]
5:     [1,2,3,4,5]| []

Following is the C++ code which implements insertion sort.

#include <iostream>
using namespace std;

void insertion_sort(int * array, int n)
{
 int i,j;
 //assume first element (index:0) is in correct position
 //start from the 2nd element (index:1)
 for( i = 1 ; i < n ; i++)
 {
  int toInsert = array[i];
  //find correct place for toInsert in arra[0:i-1] sub-array
  //j >= 0 ; make sure you have not gone beyond the beginning
  //array[j] > toInsert ; array elements greater than toInsert
  for( j = i-1 ; j >= 0 && array[j] > toInsert ; j--)
  {
   //shift array element one step right to make room for toInsert
   array[j + 1] = array[j];
  }
  //place toInsert in it's correct position
  array[j+1] = toInsert;  
 }
}
int main()
{
 int n;
 cin>>n;
 int *array = new int[n];
 int i;
 for( i = 0 ; i < n ; i++)
 {
  cin>>array[i];
 }
 insertion_sort(array,n);
 //print the sorted array
 for( i = 0 ; i < n ; i++)
 {
  cout<<array[i]<<" ";
 }
 delete[] array;
 return 0;
}