# Insertion Sort Program in C

Insertion sort program in C. Given an unsorted array, write a c program to sort an array using insertion sort.

In this tutorial, we are going to discuss following points.

i) What is insertion sort.

ii) How it’s different from Selection sort and Bubble sort.

iii) Insertion sort algorithm and it’s implementation using C program.

I have already discussed following sorting algorithms in my previous tutorials.

Bubble Sort Program in Java

Selection Sort Program in C

## What is 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 this process is repeated until complete array is sorted.

Insertion Sort –

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

ii) Requires constant memory O(1).

The time complexity of insertion sort is O(n^2).

Best Case : O(n)

Average Case : O(n2)

Worst Case : O(n2)

How Insertion Sort Works?

For example – Let’s take an array with following elements.

{6, 5, 3, 1, 8, 4}

Image taken from Wikipedia

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}

Now, All the elements of an array is sorted.

Insertion Sort Algorithm

We have discussed how insertion sort works now let’s see it’s Pseudocode.

## Insertion Sort Program in C

We have discussed how insertion sort works and it’s algorithm. Let’s write a  c program to implement insertion sort algorithm.

When to use Insertion Sort ?

Insertion sort is good for small data sets. For large data sets use more efficient sorting algorithm such as QuickSort, HeapSort and MergeSort. 