What is insertion sort. How it’s different from Selection sort and Bubble sort. I discussed selection sort and bubble in my previous posts. In this post i’ll discuss another sorting algorithm insertion sort.

Insertion sort is a simple sorting algorithm that takes one element in each iteration and put it at correct location. At each iteration it insert the element at its correct location and it repeat this process until no input element remains.

Insertion Sort –

i) Does not change the relative order of elements with equal keys.

ii) Requires **constant memory** O(1).

**Insertion Sort Time Complexity**

Best Case : O(n)

Average Case : O(n^{2})

Worst Case : O(n^{2})

** Insertion Sort Explanation **

Take elements –

6 5 3 1 8 4

**Step 1**– 5 is compared with 6 and position is swapped.

After step 1 – 5 6 3 1 8 4

**Step 2** – In next step 3 is compared with 6 and 5 and position is swapped.

After step 2 – 3 5 6 1 8 4

**Step 3** – After that, 1 is placed at correct position.

After step 3 – 1 3 5 6 8 4

**Step 4**– 8 is compared with 6 , 5 , 3, 1 . 8 is at correct position no need to swap.

After step 4 – 1 3 5 6 8 4

**Step 5** – After step 5, element 4 is paced at correct location.

After step 5 – 1 3 4 5 6 8

So all the element is sorted.

** Pseudocode for Insertion Sort **

We discussed how to do insertion sort, let’s write it’s Pseudocode.

1 2 3 4 5 6 7 8 9 10 11 12 | /* Iterate from 1 to arrlen -1 . */ for i = 1 to length(A) - 1 x = A[i] j = i-1 /* Put element at it's correct position. */ while j > 0 and A[j] > x A[j+1] = A[j] j = j - 1 A[j+1] = x |

## Insertion Sort Program in C

We have discussed how to do insertion sort and it’s pseudocode , now we can easily write it’s code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include <stdio.h> int main() { int arr[100],n,i,j,temp; printf("Enter number of elements \n"); scanf("%d",&n); printf("Enter the values \n"); for(i=0;i<n;i++){ scanf("%d",&arr[i]); } /* Insertion sort logic. */ for(i=1;i<n;i++){ temp = arr[i]; j = i - 1; while(j>=0 && temp<arr[j]){ arr[j+1] = arr[j]; --j; } arr[j+1]= temp; } /* After sorting. */ for (i=0;i<n;i++){ printf("%d ",arr[i]); } return 0; } |

**When to use Insertion Sort ?**

Insertion sort is good when you are **dealing** with **small numbers** . It’s more efficient that Selection Sort and Bubble Sort. But For large data sets use more advanced sorting algorithm such as QuickSort, HeapSort, MergeSort.