Insertion sort is a sorting algorithm that builds a final sorted array one item at a time. At each iteration through an input array, insertion sort takes one element and finds the location it belongs and inserts it.
We’ll see in a moment that insertion sort is as intuitive as sorting cards in your hand. You may not have realized it but there is a chance you applied some version of insertion sort algorithm when playing cards!
Much like selection sort, insertion sort works by dividing an input array into two virtual lists: a sorted sub-list and an unsorted sub-list.
Our sorted sub-list initially contains the first element of the input array. The rest of the elements make up the unsorted sub-list.
Insertion sort will go through the unsorted sub-list one by one, essentially removing an element from the unsorted sub-list and then inserting it into its correct position in the sorted sub-list by shifting all the elements in the sorted sub-list that are greater than the element being sorted.
We mentioned that this algorithm is as intuitive as sorting cards in your hand. Let’s look at an example by talking through our image on your right.
Imagine you have a set of cards laid out in front of you that you want to sort in ascending order. We will focus on the number and not the suit:
7, 2, 5, 8, -3. Note that our deck of cards seems to have a
-3 in it! That would make blackjack more complicated!
We can assume the first card,
7 to be a part of the sorted hand.
Next, we will look at the first unsorted element,
2, and compare it to our sorted element,
2 is smaller than
7, we’ll shift
7 one spot to the right in the sorted list and insert
2 before it.
We will continue this process for each card. We will grab the cards one by one from the unsorted hand and insert them into their correct location in the sorted hand.
The end result will be your cards sorted:
-3, 2, 5, 7, 8