Insertion sort is a simple comparison sorting algorithm, that considers at a step k, the elements of the array A[0,k-1] are already sorted out, and the element on the k position will be inserted that way that after the insertion, the elements A[0,k] are sorted out.

Inserting the k element in the A[0,k-1] sequence requires a few steps:

- the element must be retained in a temporal variable;
- moving all the elements from the A[0,k-1] array that are greater than A[k] with a position to the right (this presumes a run from right to left of the array);
- placing the A[k] element on the former spot of the last element that moved.

### Step by step example :

Having the following list, let’s try to use insertion sort to arrange the numbers from lowest to greatest:

Unsorted list: __6__ **4** 5
10 3 1 8 9 7 2

Step 1:

4 __6__ **5** 10
3 1 8 9 7 2 – As 6 was the first element, at step 1, the element 4 is being
inserted, and 4 is smaller than 6, so it must place before 6, so the order would
be 4 6.

Step 2:

4 5 __6__ **10** 3
1 8 9 7 2 – At step 2, 5 was the element to be inserted, and being smaller than
6, it goes before it, but then it is compared to 4 which is smaller than 5, now
the order would be 4 5 6.

Step 3:

4 5 6 __10__ **3** 1
8 9 7 2 – At step 3, 10 was the new element, and being greater than 6, the
element was in the right place and no moving had to take place, now the order
would be 4 5 6 .

Step 4:

3 4 5 6 __10__ **1** 8
9 7 2 – At step 4, 3 was the new element, and compared to 10 it is smaller, so
it has to move to the left, also, it is compared to 6 then to 5 and then to 4,
and is smaller than any of these, so the position of the element 3 is at the
left of all these numbers, now the order would be 3 4 5 6.

Step 5:

1 3 4 5 6 __10__ **8** 9
7 2 – Step 5, the new element is 1, which is again smaller than 10, then like in
the previous steps, it is compared to the next numbers 6,5,4,3 and is smaller
than an of these, so it ends at the left of the array that has been sorted out
so far, with the order being 1 3 4 5 6

Step 6:

1 3 4 5 6 8 __10__ **9** 7
2 – At step 6, the element 8 was compared to 10 and moved to the left, but
compared to 6 it is greater, so now the list would look like 1 3 4 5 6 8

Step 7:

1 3 4 5 6 8 9 __10__ **7** 2
– Step 7, the element 9 was compared to 10 and moved to the left having it being
smaller, but it is greater than 8 so the list is : 1 3 4 5 6 8 9

Step 8:

1 3 4 5 6 7 8 9 __10__ **2** –
Step 8, the element of 7 was compared to 10, so it had to move to the left of
10, also 7 is smaller than 8 which it moves another position to the left, but it
is greater than 6, so it found its position, with the array looking like : 1 3 4
5 6 7 8 9

Step 9:

1 2 3 4 5 6 7 8 9 __10__ –
At the final step 9, the element 2 was compared to 10, being smaller it moves to
the left, then again it is compared to 9, then 8, 7, 6, 5, 4, 3 and is smaller
than any of these numbers, so the right position is to the left, but being
greater than 1, it’s at one position to the right of the element 1, now the
final order is the right one : 1 2 3 4 5 6 7 8 9 10

Having no more elements to compare 10 to, the algorithm now knows that the list is sorted.

### Sample code:

`#include < iostream >`

using namespace std;

int main(void)

`{`

int i;

long int A[100];

long int n=100;

cout << "Please insert the number of elements to be sorted: ";

cin >> n; // The total number of elements

for(int i=0;i < n;i++)

`{`

cout << "Input " << i << " element: ";

cin >> A[i]; // Adding the elements to the array

`}`

cout << "Unsorted list:" << endl; // Displaying the unsorted array

for(int i=0;i < n;i++)

`{`

cout << A[i] << " ";

`}`

for (int k=1;k < n;k++)

`{`

int temp=A[k]; // the k element to be inserted is retained in a temporal variable,

i = k-1; //at first it is the A[1] value, which is the second value of the array

while (i >=0 && A[i] > temp)

`{`

A[i+1] = A[i];

i = i-1;

`}`

A[i+1] = temp;

`}`

cout << "Sorted list:" << endl; // Displaying the sorted array

for(int i=0;i < n;i++)

`{`

cout << A[i] << " ";

`}`

return 0;

`}`

### Output:

### Code explanation:

for (int k=1;k < n;k++)

`{`

int temp=A[k];

i = k-1;

while (i >=0 && A[i] > temp)

`{`

A[i+1] = A[i];

i = i-1;

`}`

A[i+1] = temp;

`}`

The temp variable retains the value to be inserted, which at the first run of the loop would be A[1], being the second value as A[0] is the first value. Then the while loop checks to see if A[0] is greater than A[1], and if it is true, a swap between the values takes place. Also, i is decremented by 1. At the next run, A[2] is compared to A[1], and if it is greater a swap takes place, and after that it is compared to A[0], and if its greater there is a swap between the values, if not, the proper order has been found out.

### Complexity:

How many compares are done? 1+2+…+(n-1) which results in O(n^2) worst case and (n-1)* 1 which is O(n) on best case. Also, how many element shifts are done? 1+2+…+(n-1) on O(n^2) worst case and 0 , O(1) best case.

### Advantages:

- it is easy to learn;
- few lines of code;
- efficient for small data sets;
- stable, does not change the relative order of elements with equal keys;

### Disadvantages:

- not effective for large numbers of sorting elements;
- needs a large number of element shifts;
- as the number of elements increases the performance of the program would be slow.

### Conclusion:

Like bubble sort, insertion sort is also a simple comparison algorithm. Unfortunately, it is not quite efficient on large lists, but it is an easy sorting algorithm to learn. The best case would be that the list was already sorted, meaning it would only have to traverse the list as oppose to traverse and swap. Worst case is achieved because regardless it has to traverse as well as swap through the entire list.