**INTRODUCTION**

In this tutorial, we are going to learn about the insertion sort algorithm. It is a simple and efficient algorithm which is widely used for sorting elements. The implementation of the insertion sort algorithm works similarly as we sort out cards, we assume that the first card is already sorted, and then we arrange all the unsorted cards in their respective positions on comparing with the sorted card.

The implementation of the insertion sort algorithm mainly follows two portions.

- Sorted portion

2. unsorted portion

**Initially, the first element of the array is considered the sorted portion and it is compared with the next element to it. If the next element is placed in a suitable order, then it is not disturbed, otherwise, it is swapped with the left element according to the condition.**

Let’s understand *the working of the **insertion ***sort** with an example.

Let’s consider these are the elements of an array.

`Arr= [23 ,56 ,32 ,78 ,12]`

in the *first pass*, **23 ** is compared with **56**. as **23 < 56,** both elements are considered to be in ascending order and hence swapping doesn’t occurs. Then **56 **is also considered to be in the sorted portion.

```
23 56 32 78 12
23 56 32 78 12
```

In the *second pass*, **56 **is compared with **32. **as **56>32, **swapping occurs. After swapping **56 and 32, **the position of elements looks like this.

```
23 56 32 78 12
23 32 56 78 12
```

Now, **32 **is also compared with **23. **since **23<32, **swapping doesn’t occur and the elements after the second pass are arranged as follows.

```
23 32 56 78 12
23 32 56 78 12
```

In the *third pass*, **56** is compared with **78**. as **56<78**, both elements are considered to be in ascending order and hence swapping doesn’t occurs. Then, **78** is also considered to be in the sorted portion

```
23 12 32 78 56
12 23 32 56 78
12 23 32 56 78
12 23 32 56 78
12 23 32 56 78
```

In the *fourth pass, ***78** is compared with **12**. as **78>12**, swapping of the elements occurs and after swapping, the positioning of the elements looks like this.

```
23 32 56 78 12
23 32 56 12 78
```

Now, **12** is compared with **56** too. As **56>12,** swapping of the elements is done.

```
23 32 56 12 78
23 32 12 56 78
```

Now, **12** is compared with** 32** and swapping occurs as **32>12**.

```
23 32 12 56 78
23 12 32 56 78
```

And **12** is compared with the last element left, **23** and **23>12**, so swapping occurs.

```
23 12 32 56 78
12 23 32 56 78
```

After the fourth pass, the elements are already in sorted order and after all the traversals, the positioning of the elements of the array looks like this.

The sorted array is **12 23 32 56 78**

this is the working of the bubble sort algorithm. Now, let’s look at the algorithm for the Insertion sort.

## ALGORITHM

```
Step 1: Start.
Step 2: Take the first element and compare it with the next element. If the current element is larger than the next element, swap those positions and also compare with the elements on the left side of the current element.
Step 3: If the elements on the left are also larger than the current element, swap those elements one by one until the current element reaches the intended position.
Step 4: Stop.
```

Let’s look at the code implementing the bubble sort algorithm.

C++ Code:

```
#include <iostream>
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for(int i = 0 ; i<n ; i++) cin>>a[i];
for (int i = 0; i < n ; i++) {
int j = i;
while (j > 0 && a[j - 1] > a[j]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
j--;
}
}
for(int i = 0 ; i<n ; i++) cout<<a[i]<<" ";
}
```

JAVA code:

```
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int a[];
a = new int[n];
for(int i = 0 ; i<n ; i++) a[i] = s.nextInt();
for (int i = 0; i < n ; i++) {
int j = i;
while (j > 0 && a[j - 1] > a[j]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
j--;
}
}
for(int i = 0 ; i<n ; i++) System.out.print(a[i]+" ");
}
}
```

Python code

```
n = int(input())
a = []
for i in range(n):
x = int(input())
a.append(x)
for i in range(n):
j = i
while (j > 0 and a[j - 1] > a[j]):
temp = a[j-1]
a[j-1] = a[j]
a[j] = temp
j = j-1
for i in range(n):
print(a[i],end=' ')
```

```
Input: 5
23 56 32 78 12
Output: 12 23 32 56 78
The time complexity of the code is O(n2) as here we use the nested for loops.
The space complexity of the code is O(1).
```

*ADVANTAGES*

*ADVANTAGES*- As the insertion sort algorithm is an in-place algorithm, there is no need for extra space.
- The insertion sort algorithm efficiently works over a small set of elements.

Now let’s look at the disadvantages of the bubble sort.

*DISADVANTAGES*

*DISADVANTAGES*- The insertion sort algorithm is very less efficient as it uses nested loops which increases the time complexity of the code.
- Performance of the insertion sort algorithm is also based on the ordering of the elements in the list.
- The insertion sort algorithm is less efficient when we use a large number of elements in the data set for sorting.

**CONCLUSION**

That’s it from this tutorial. Hope you guys found It interesting. We have learned about the insertion sort algorithm, its implementation, advantages and disadvantages of the insertion sort algorithm and we have solved the insertion sort algorithm in different programming languages. Happy coding!