# 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.

### Complexity table of Insertion sort

Complexity | Best case | Average case | Worst case |

Time | O(n) | O(n^{2}) | O(n^{2}) |

Space | O(1) |

### 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.

11 | 8 | 6 | 1 | 9 | 2 |

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.

Iteration 1: Since 8 is smaller than 11, it will change its place among themselves. 8 11 6 1 9 2 Iteration 2: Now, you will compare the next two elements (11 and 6). Since 6 is smaller than 11, it will change its place among themselves. After this, 8 and 6 will compare, 6 is smaller than 8, so it will change its place among themselves.6 8 11 1 9 2 Iteration 3: Now, you will compare 11 and 1. Since 1 is smaller than 11, it will change its place among themselves. After this, 8 and 1 will compare, 1 is smaller than 8, so it will change its place among themselves. 1 6 8 11 9 2 Iteration 4: Now, you will compare 11 and 9. Since 9 is smaller than 11, it will change its place among themselves. 1 6 8 9 11 2 Iteration 5: Now, you will compare 11 and 2. Since 2 is smaller than 11, it will change its place among themselves. After this, 9 and 2 will compare, 2 is smaller than 9, so it will change its place among themselves. 1 2 6 8 9 11 |

#### Insertion sort program in C language:

#include<stdio.h> void main () { int i, j, k, temp; int a[6] = { 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