Insertion Sort

It is a comparison sorting algorithm that works on a sorted array or a list. It is not very efficient on large lists but has many advantages. Few of them are:

Small data can be efficiently sorted
It runs O(n+d) time where d is the number of inversions and works on an already sorted array or list.
It is more efficient than algorithms with O(n²) complexity.

# Working of Insertion Sort

In insertion sort, to find the correct position we search till the last item just greater than the targeted item is found. Then we shift all the items from point one, down the list and then insert the targeted item at the vacant place.

# Program to show Insertion Sort

#include<iostream.h>
using namespace std;
void insertion_Sort(int array[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = array[i];

j = i - 1;

while (j &gt;= 0 &amp;&amp; array[j] &gt; key)

{

  array[j + 1] = array[j];

  j = j - 1;

}

array[j + 1] = key;

}
}
void disp_arr(int array[], int n)
{
int i;
for (i = 0; i < n; i++)
cout &lt;&lt; array[i] &lt;&lt; " ";

cout << endl;
}
int main()
{
int array[] = {
60,
20,
30,
10,
12
};
int n = sizeof(array) / sizeof(array[0]);
insertion_Sort(array, n);
disp_arr(array, n);
return 0;
}