In this tutorial, we will learn about another sorting algorithm called insertion sort. Although insertion sort is not one of the best sorting algorithm in terms of performance but it is more efficient than selection and bubble sort in practical scenarios. It uses a sorting technique that is very practical and intuition based.

## Understanding Insertion Sort

To understand insertion sort in an easier manner, we will use the practical example of playing cards.

Assume we have the following set of cards.

Our aim is to arrange these cards in increasing order of rank.

### Sorting playing cards using two sides

There are many ways to sort this set of cards. One way is to keep all the cards in our left hand and start taking cards one by one from the left hand to the right hand to form a sorted arrangement in the right hand.

Our first card is ‘5’ and there is no other card in our right hand to compare it with hence it will simply move to the right irrespective of position.

Now the next card in our left hand which is 2. We will take this 2 to the right hand but make sure to insert it before 5 to make sure the cards are sorted in increasing order of values. At any stage during this whole process, the left hand will be unsorted and the right hand will be sorted.

Now we will move 8 to the other side. It will be placed after 5 to follow the sorting arrangement.

Lastly, we will move the card 7 from the left side to the right. In the right sorted side it will be inserted between 5 and 7. Finally, we will have a sorted arrangement in the right hand.

### Sorting Playing cards using single side

Now lets demonstrate this whole process using only single side. The main idea is to divide the cards into two subsets: a sorted part and an unsorted part. Initially all the cards are in the unsorted part separated by the vertical line as shown in the figure below. We are picking one card at a time from the unsorted part and putting it in the sorted part. The first card will be simply moved to the other side and the rest of the cards will be follow suite and be placed in their appropriate position after being compared with each element.

The first card in our unsorted part is 5. It will simply be moved to the sorted side.

The next card is 2. It is lesser than 5 hence it will be placed before 5 in the sorted part.

The next card in the unsorted part is 8. It will be placed after 5 in the sorted part.

The last card in the unsorted part is 7. As it is lesser than 8 and greater than 5 hence it will be inserted between these two cards in the sorted part.

Once the unsorted part is empty we will be done with our sorting process. As you may see the cards are all sorted in increasing order of values.

### Sorting list of integers using Insertion sort

Lets apply this same logic to sort a list of integers. Suppose we have an array of 5 integers named X with un ordered numbers. Our aim is to sort the following numbers in increasing order of values by using insertion sort algorithm.

Our array has 5 elements so we have indices from 0 to 4. Now the first thing that we will do is divide this array into two parts: the unsorted part and the sorted part as we did in the playing cards scenario. The elements till index 0 will be part of the sorted half. We will pick elements from the unsorted part and keep on inserting them into the sorted part. In this way the sorted part will keep on increasing until the unsorted part becomes empty.

At any stage the cells shown in white will be part of the sorted subset and the rest will be part of the unsorted subset. Initially, the element in index 0 constitutes the sorted part and index 1 to index 4 are part of the unsorted subset.

The first element in our unsorted part is at index 1 that is ‘1’. While programming this value will get stored in some variable for example ‘value.’ In this particular case, value = X[1]. To understand this in a better way we can assume that the value at index 1 has been replaced by an empty hole.

Now we will insert the value at index 1 into the sorted part of the array and shift all the elements greater than 1 in the sorted part by one position to the right. At this stage we have only one element in the sorted part which is ‘4’. 4 is greater than 1, hence it will be shifted one position to the right at index 1 and the hole will move to index 0 instead.

Then we will place 1 back at the hole position at index 0. Now index 0 till index 1 are part of the sorted subset and index 2 till index 4 are part of the unsorted subset.

Now the first element in the unsorted part is 5 at index 2. We will again create a hole at its place and save it in the variable value. At this point we are assuming that we have placed the value 5 in the variable value and its position is filled with a hole.

All the elements greater than 5 will be shifted one position to the right one by one. At index 1 we have 4. It is lesser than 5 hence it will not be shifted. At index 0 we have 1. It is also lesser than 5 hence it will also not be shifted. As no elements in the sorted part are greater than 5 therefore they will remain in their current positions. Now 5 will be placed back at the hole position which is index 2. Elements till index 2 are part of the sorted subset and from index 3 till index 4 are part of the unsorted subset.

Once again we will do the same process again. Now the first element in the unsorted part is 2 at index 3. We will again create a hole at its place and save it in the variable value. At this point we are assuming that we have placed the value 2 in the variable value and its position is filled with a hole.

All the elements greater than 2 will be shifted one position to the right one by one. At index 2 we have 5. It is greater than 2 hence it will move right by one position to index 3 and hole will come in the position of index 2.

At index 1 we have 4. It is also greater than 2 hence it will also move to the right by one position and end up at index 2. The hole will therefore move to index 1 instead.

At index 0 we have 1. As it is lesser than 2 hence it will not shift. Now 2 will be placed back at the hole position which is index 1. Elements till index 3 are part of the sorted subset and the element at index 4 is part of the unsorted subset.

Now lets do the same process again one last time. Now the first and only element in the unsorted part is 3 at index 4. We will again create a hole at its place and save it in the variable value. At this point we are assuming that we have placed the value 3 in the variable value and its position is filled with a hole.

All the elements greater than 3 will be shifted one position to the right one by one. At index 3 we have 5. It is greater than 3 hence it will move right by one position to index 4 and hole will come in the position of index 3.

At index 2 we have 4. It is also greater than 3 hence it will also move to the right by one position and end up at index 3. The hole will therefore move to index 2 instead.

At index 1 we have 2. As it is lesser than 3 hence it will not shift. At index 0 we have 1. It is also less than 3 therefore it will stay in its position. We have no more elements greater than 3 hence no more shifting will be required. Now 3 will be placed back at the hole position which is index 2. Our list is now sorted.

This particular in-place logic of shifting and inserting elements to sort a list is known as insertion sort.

## Pseudocode Insertion Sort Algorithm

Below you can view the pseudocode for the insertion sort algorithm:

```
InsertionSort(X,n)
{
for i=1 to n-1
{
value=X[i]
hole=i
while(hole>0 && X[hole-1]>value)
{
X[hole]=X[hole-1]
hole=hole-1
}
X[hole]=value
}
}
```

The InsertionSort() function will take in two arguments. The first argument will be the array and the second argument will be the number of elements in the array. Initially we are saying that we are sorted till index 0. Therefore, we will pick elements from 1 till (n-1). At each step we will insert the element at its appropriate position in the sorted part.

For this feature we will use a for loop and run it from i=1 to (n-1). Inside this loop we will create a hole by taking out the value to insert in another variable. We will define a variable called ‘value’ and store X[1] in it. We will also need another variable to monitor the position of the hole. This variable we are naming as ‘hole’. Now at this stage, the hole is at index i and will be shifted in case an element in the sorted part is greater than the value saved in the variable ‘value.’ The hole will move to index position of that particular element and that element will move to the right by one index. This logic will be taken care of in the while statement which is as follows:

```
while(hole>0 && X[hole-1]>value)
{
X[hole]=X[hole-1]
hole=hole-1
}
```

while the hole is greater than 0 and the element at index (hole-1) is grater than the value, we will shift the element at the index (hole-1) to index hole. Therefore the hole will now be at index (hole-1).

If this condition is not true, which means the particular element in the sorted part is smaller than the value or the hole reaches index 0. then the loop will be exited. After exiting the whole loop, the value saved in the variable ‘value’ will be stored back at the index the hole was currently i.e. X[hole].

### Time complexity

To monitor the time complexity of Insertion Sort algorithm we will make use of the pseudocode given above. The total running time of this algorithm will be the total running time of the statements.

- Assuming the following statements take a constant time C1 to execute. These statements will always run (n-1) times.

```
value=X[i]
hole=i
```

- Similarly, lets assume that the following statements take a constant time C2 to execute:

```
X[hole]=X[hole-1]
hole=hole-1
```

- Likewise, this particular statement takes a constant time C3 to execute. This statement will also always run (n-1) times.

`X[hole]=value`

In the best case considering the array is already sorted, the program will not enter the while loop hence we will not consider C2 in that case. Therefore the running time for best case will be:

T(n) = (C1+C3)*(n-1)

= an + b

Thus, we can say that the time complexity for best case is O(highest order) so O(n).

For the worst case, the total running time will be:

T(n) = (C1+C3)*(n-1) + [1+2+3+4+…+(n-1)]*C2

= (C1+C3)*(n-1) + [n*(n-1)]/2

= an^2 + bn +c

Thus, we can say that the time complexity for worst case is O(highest order) so O(n^2).

In an average case, for the i-th position we will make i/2 shifts therefore the total running time will still be of the form an^2+bn+c. Therefore, for average case the time complexity will also be O(n^2).

Although Insertion sort has a similar time complexity as that of selection sort and bubble sort however it takes lesser amounts of comparisons for the list to get sorted completely.

## Insertion Sort C Example

```
#include <stdio.h>
void insertion_sot(int arr[], int size)
{
int i, j, temp;
for (i = 1; i < size; i++)
{
temp = arr[i];
j = i - 1;
while(j>=0 && temp <= arr[j])
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = temp;
}
}
void print_Arry(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before Sorting array: - \n");
print_Arry(a, n);
insertion_sot(a, n);
printf("\nAfter sorting array : - \n");
print_Arry(a, n);
return 0;
}
```

```
Before Sorting array: -
12 31 25 8 32 17
After sorting array : -
8 12 17 25 31 32
```