Explanation of the Insertion Sort Algorithm:
The simple steps of achieving the insertion sort are listed as follows -
Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step2 - Pick the next element, and store it separately in a key.
Step3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then move to the next element. Else, shift greater elements in the array towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.
Working of Insertion sort Algorithm
Now, let's see the working of the insertion sort Algorithm.
To understand the working of the insertion sort algorithm, let's take an unsorted array. It will be easier to understand the insertion sort via an example.
Let the elements of array are -
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort.png)
Initially, the first two elements are compared in insertion sort.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort2.png)
Here, 31 is greater than 12. That means both elements are already in ascending order. So, for now, 12 is stored in a sorted sub-array.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort3.png)
Now, move to the next two elements and compare them.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort4.png)
Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along with swapping, insertion sort will also check it with all elements in the sorted array.
![]() |
For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence, the sorted array remains sorted after swapping.
Now, two elements in the sorted array are 12 and 25. Move forward to the next elements that are 31 and 8.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort6.png)
Both 31 and 8 are not sorted. So, swap them.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort7.png)
After swapping, elements 25 and 8 are unsorted.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort8.png)
So, swap them.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort9.png)
Now, elements 12 and 8 are unsorted.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort10.png)
So, swap them too.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort11.png)
Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that are 31 and 32.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort12.png)
Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort13.png)
Move to the next elements that are 32 and 17.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort14.png)
17 is smaller than 32. So, swap them.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort15.png)
Swapping makes 31 and 17 unsorted. So, swap them too.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort16.png)
Now, swapping makes 25 and 17 unsorted. So, perform swapping again.
![Insertion Sort Algorithm](https://static.javatpoint.com/ds/images/insertion-sort17.png)
Now, the array is completely sorted