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

ComplexityBest caseAverage caseWorst case
TimeO(n)O(n2)O(n2)
Space  O(1)

Insertion sort algorithm

Insertion sort example

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

1186192

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:

Output

Insertion sort program in java language:

Output

Pin It on Pinterest

Share This