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:  | [1,5,2,4]
2: [1,3] | [5,2,4]
3: [1,3,5] | [2,4]
4: [1,2,3,5] | 
5: [1,2,3,4,5]| 
Following is the C++ code which implements insertion sort.