Insertion Sort Pseudocode

This is the second of two videos about the insertion sort. It builds on the previous video, which illustrated the algorithm for an insertion sort, by describing the pseudocode for an insertion sort. This video illustrates how a pointer variable separates the sorted and unsorted sections of a list. It shows how the pointer advances from left to right, making each item in the unsorted section the current item, as the insertion sort progresses. A defining characteristic of the insertion sort is that that sorted section of the list is scanned from RIGHT TO LEFT. You can therefore recognise the code for an insertion sort because you’ll see a variable being DECREMENTED within a nested loop. The insertion sort is like sorting a hand of playing cards. The insertion sort is particularly good for lists that are nearly sorted already, or when you just want to insert a single item into a list that is already in order. For example, the high score board of a game would be a good candidate for an insertion sort. The insertion sort is a little faster than a bubble sort but, like the bubble sort, the insertion sort does not scale well. It is not the best choice for a very large list.