Insertion Sort

Under Insertion sort, the sub-list of an array is always kept sorted. Now any new element that is to be added to the list will have to find an appropriate place for itself. How will we do that? We will check every element of the list with the new element and will fit it to a place that is meant for it.


Example: If you have a deck of 5 cards in your hands in a sorted order, you are told to insert another element into the list in its sorted place. To insert that card, you will check the whole list to find the sorted position of this card. A similar concept is used in the Insertion Sort.


Working:

We will now learn the step-by-step process of Insertion sort. Assume that we have an unsorted array given below.

Insertion Sort Example

So in the first step, the first two elements of the array are checked. As they are already in the ascending order the sub-list of the array is sorted.

insertion sort example

Now, we move to the next element which is 26, 26 and 32 are compared and as 26 is smaller, it is swapped with 32.

insertion sort example

26 is now compared with the subarray element 13 as well and if smaller it is swapped as well. After this iteration, the array becomes:

insertion sort example

The first position of the array is sorted now thus we move to the next part. 32 is now compared with 9 and the same process continues.

insertion sort example

now, 9 is swapped with 32 and is then checked with 26. 9 being smaller is swapped with 26 and so on.

insertion sort example

next iteration:

insertion sort example

last iteration:

insertion sort example

 

This process continues until all the elements of the array are sorted. 

Algorithm

Let's check out how the sorting algorithm works,

Step1: The first element of the array is already sorted. Return 1.


Step2: Pick the next element.


Step3: Compare with all elements of the sub-sorted array.


Step4: Swap all the elements of the sub-sorted array to make the array in ascending order.


Step5: Repeat until the list is sorted.