Insertion Sort Working Mechanism

For Complete YouTube Video: Click Here

In this class, we will try to understand Insertion Sort Working Mechanism.

We have already discusssed Selection and Bubble sort algorithms in our previous classes.

Insertion Sort Working Mechanism

The Insertion Sort Working Mechanism resembles the real world example of arranging the playing cards.

For example consider a deck of cards.

Now by taking each card at a time from the top of the deck we will arrange them in the sequence.

We will compare the card from the top of the deck with all the cards in the hand and insert it in the corresponding position.

In the same way we will arrange the elements in the array.

For better understanding of Insertion Sort Working Mechanism we will consider the array of elements shown below.

We will start with the element in the index one which is three.

Three is compared with the elements on the left of the key element.

The elements on the left of the key element are the elements that are already in the order.

Now three is compared with six.

If the key element is less than the element in the array the element in the array will be moved to the key elements position.

This comaprision will be done if the all the elements in the left of the array are completed or if the one of the element in the left part of the array are smaller than the key element.

Because the elements on the left part of the array are in the sorted order if the element in the array is lesser means this is the index where the key element has to placed.

As 6 > 3 six will be shifted to the keys position.

As there are no elements further the three will be placed in the 0th index.

Now consider the element in the third index which is nine.

Now, nine is the key element for which we have find its position.

Compare nine with all the elements to the left part of the array.

6 > 9 is false so further comaprisions is not required.

Because the elements on the left side of the array are in sorted order and 6 > 9 is false means all the remaining elements are smaller than nine.

Nine is in its exact position.

Now the element in the index four which is 10 is the key element.

Ten is also in its position.

Now the element in the fifth index is the key element.

Two is the key element.

10 > 2 is true so ten will be shifted to the keys position.

9 > 2 is true so nine will be shifted to the element 10 position.

6 > 2 is true so six will be shifted to the element 9 position.

3 > 2 is true so three will be shifted to the element 6 position.

As there are no further elements to be compared two is placed in the 0th index.

In the same way the element in the 5th index will be placed in its exact position.

For better understanding click the YouTube link provided on the top.