Insertion Sort

Insertion Sort Process

Imagine that you have a deck of 10 numbered cards that are completely sorted, except for the last card placed face-down in front of you.

Now, you don't know what the value is on any of the cards, only that the last card is not in the correct place. Additionally, you are only allowed to have 2 cards facing up at any time. How would you sort them?

Most likely, you'd flip over the last card and then flip over other cards throughout the pile until you find the correct place.

To make this more procedural, what if we started comparing the last card to the end of the sorted cards, then moved toward the front of the pile until we find a card with a smaller value? Once we find one, it is guaranteed that our card goes immediately after it in the order, since we know all the other cards are sorted.

If we run out of cards to compare, we know that the card is the smallest value in the pile, so it goes at the front.

This is fine for sorting one card into a stack, but what if the entire pile were mixed up?

If we look at the last card, we have no other information about the pile to work off, so we're stuck. Instead, we should start smaller.

What if we consider just the first card by itself? It might sound strange, but the first card makes up a pile of 1 card that is completely sorted.

We could then take the second card and sort it in the way we discussed before, as we have a sorted list with only the last card out of order.

This will then give us a pile of 2 sorted cards. We can repeat this process of grabbing one new card and sorting it in the pile until all the cards are sorted. For example, the next step would look like:

This algorithm is known as Insertion Sort.

Insertion Sort Visualization

You can sort the next value by pressing the Step button, undo the last value sorted by pressing the Step Back button, or continue to step through using the Play button. Additionally, while it is running, you can press the Stop button or Skip button to pause or skip the animation. The slider controls the animation speed, and the bottom set of buttons are data presets, to see how the algorithm works on different data. The yellow circle represents the current/next value to be sorted. While the animation is playing, colored circles will represent what values the algorithm is currently comparing, and they will be red if a the compared value is larger or green if it is smaller.

Insertion Sort Time and Space Complexity

Insertion Sort is often considered one of the simplest sorting algorithms, and is often used in the real world for sorting hands of cards, without people usually realizing. Insertion Sort is quite fast at sorting small lists, but slows down quickly as the amount of values increases. Sometimes it is combined with merge sort to utilize its speed for small lists and merge sort's speed for large lists.

Insertion Sort has a time complexity of $O(n^2)$ due to $O(n)$ values needing to be sorted and an average of $O(n)$ comparisons per sorted value. Similar to Bubble Sort, Insertion Sort has an average space complexity of $O(1)$, as only one temporary value is needed for any given swap.