How the Insertion Sort Works?

Hello!

I’m writing this post to show how insertion sort works.

First of all, you should get to know what is insertion sort?

What is Insertion Sort?

It is a simple sorting algorithm which can be used to sort a small set of numbers.

We can connect this with playing cards. Imagine you have a set of cards which are placed upside down on a table. You have to pick one card from the set at a time. Once you have picked the first card, you don’t need to do anything. Once you have picked the second one, you compare the card with which is in your hand. Likewise, you pick up every card and compare with the set of cards in your hand and arrange accordingly.

It’s so simple. This is how insertion sort also works.

Let’s see the actual working now.

You have 5 numbers stored in an array.

5

4

2

1

3

You start with the value in index 0, that is number 5. Since you have only one number no need to compare and swap.

Let’s move on to the next index 1, the number is 4. Now, you compare 4 and 5.

4 < 5 Therefore, you need to swap.

4

5

2

1

3

2 < 5 therefore, swap.

4

2

5

1

3

2

4

5

1

3

Now the next number in index 3 is 1. Compare with 5 first.

1 < 5, so swap!!
              0                           1                           2                            3                             4

2

4

1

5

3

1 < 4, swap!!

2

1

4

5

3

1 < 2, swap!!

1

2

4

5

3

Move on to last index 4. The number is 3. Compare.

3 < 5, swap.
              0                           1                            2                            3                            4

1

2

4

3

5

Compare 3 with 4 now.

3 < 4, swap.

1

2

3

4

5

Finally, you have now sorted array. This is how simple insertion sort works.