# Insertion sort

Insertion sort is a simple sorting technique. It is best suited for small data sets, but it does not suitable for large data sets. In this technique, we pick an element and insert it in its appropriate place. Insertion sort is not a fast sorting algorithm because it uses the nested loops to shift the elements in their place. But this is a better sorting technique than bubble sort and selection sort because the complexity of insertion sort is less than both.

If you have n elements in the array, you will need (n-1) pass to sort it.

### Insertion sort algorithm

```Insertion_sort(A)
{
Repeat for i = 2 to the length of A
{
item = A[i]
j = i – 1
Repeat while (j>0 and A[j] > item)

{
A[j+1] = A[j]
j = j – 1
} // end of while loop
A[j+1] = item
} // end of for loop
} // end of the insertion loop  ```

### Insertion sort example

Suppose you have the following array, which you have to sort.

In insertion sort, the first two elements are compared.

There are 6 elements in this array, so you will need 5 iterations to sort it.

#### Insertion sort program in C language:

```#include<stdio.h>
void main ()
{
int i, j, k, temp;
int a = { 11, 8, 6, 1, 9, 2};
printf("\n Insertion sort  \n");
for(k=1; k<6; k++)
{
temp = a[k];
j= k-1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
for(i=0;i<6;i++)
{
printf("\n%d\n",a[i]);
}
}    ```

Output

```Insertion sort
1
2
6
8
9
11```

#### Insertion sort program in java language:

```public class InsertionSort
{
public static void main(String[] args)
{
int[] a = {11, 8, 6, 1, 9, 2};

for(int k=1; k<10; k++)
{
int temp = a[k];

int j= k-1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
System.out.println("Insertion sort ");
for(int i=0;i<10;i++)
{
System.out.println(a[i]);
}
}
}    ```

Output

```Insertion sort
1
2
6
8
9
11```