# Insertion Sort Program, Algorithm, Time Complexity

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(n2)

Worst Case : O(n2)

Insertion Sort Explanation

Take elements –

6 5 3 1 8 4

Subscribe Our Tutorials

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.

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

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.