Insertion sort is as intuitive as sorting a hand of cards. In real life, we just create space and insert a card into the correct position.

If you were sorting cards on a table, it’s pretty easy to insert your card into the correct position. You might not even realize you are shifting every other card down one!

However, when coding this algorithm, this idea of shifting every element to the right is one of the trickiest parts to implement.

If we take a look at the illustration we can look at what happens when we get to the final unsorted card, -3.

We need to find the correct place to insert it.

8 > -3 so we shift 8 to the right.
7 > -3 so we shift 7 to the right.
5 > -3 so we shift 5 to the right.
2 > -3 so we shift 2 to the right.

We have now reached the front of the cards and there is nowhere further to go so we insert our -3.

This highlights two conditions we will need to account for in our code before we make our switch:

• Is the already sorted item greater than the item we are attempting to sort? If so, shift it to the right. If not, insert the new card after the already sorted card.
• Have we reached the beginning of our array? If so, insert the card.