Introduction to insertion sort

In this step, you are going to have a look at another popular algorithm for sorting a list of items — insertion sort.

The insertion sort algorithm demonstrates to learners how the downfalls of bubble sort can be improved upon, it does away with the excess looping over the entire list that features so prominently in bubble sort.

An introduction to insertion sort

The insertion sort algorithm will split the list to be sorted into two sections, called sublists. These are not separate list variables, rather they are two parts of the original list — a sorted sublist and an unsorted sublist. The sorted sublist starts with just one item (the first in the list) and the rest of the list is in the unsorted sublist.

As the algorithm progresses, each item is evaluated and inserted into the correct place in the ordered sublist.

Consider the following list of playing cards. I am going to use insertion sort to put them in ascending order.

1. The first card in the list is already in the sorted sublist, and because it is the only card it is already sorted. So I start by grabbing the second card in the list, which is the start of the unsorted sublist.

2. I then compare the card in my hand to the cards prior to it (in the sorted sublist) of which there is only one at the moment. So I would compare the 3 to the 9 card.

Because the previous card has a higher value than the card I am trying to sort, I move the 9 over one place to the right. This frees up the slot for my current card at the start of the list.

3. I then move on to the next card in the unsorted sublist. In this case it is the third card, which is a 10.

Insertion sort works by shifting cards in the sorted list that are larger than my current card. Instead of starting at the first item in the list instead I start from the end of the sorted list and work backwards. The first comparison I would make is 9 > 10.

The result being that 9 is less than 10 so the cards are already in the correct order and no shifts are needed. I place the card back in its original place and this becomes the end of the sorted sublist.

4. The process repeats and I pick up the next card in the unsorted sublist — a 2 — and compare the value with the cards in the sorted sublist starting at the end.

First I compare the 10 with my 2. Because 10 is higher I shift the 10 card one spot to the right and continue with my comparisons.

Next I compare 9 with my current card, again the sorted card (9) has a higher value than my 2 so the 9 card is shifted one spot to the right and I carry on.

Finally I compare the first card in the sorted list 3 with my card — 2. The 3 has a higher value so I move it one spot to the right, there are no more cards left to compare so I place the 2 at the start of the list.

Hopefully you can see the pattern emerging in the process of this algorithm and how to find the right place to insert the card.

5. I pick up the next card (8) and compare it to the last item in the sorted section (10). The result is that 10 is larger, so I move the 10 to the right and continue.

The next comparison is 9 > 8 and again the result is that the 9 is greater and so I move it and continue comparing.

I then look at the 3 card and see that its value is less than my current card, so I place my 8 in the list in the space that is currently free. This leaves the sorted sublist as 2, 3, 8, 9, and 10.

For the last few steps, I will not go into the same level of detail, but be aware that I would still follow the same process.

6. The next unsorted card is 5 — I travel back down the sorted list comparing as I go. All of them are larger than my 5 until I get to the 3 card. At this point I have found the space for my 5.

7. The final card in the unsorted sublist is 1 and I repeat the process of comparisons. Heading down the list I find that all the items are larger than my 1, so as I go I move each card one space to the right until I am left with an empty space at the end of the list.

<- previous

next ->