Insertion Sort

by Mirabelle Jones

Following selection sort and bubble sort (which are worth jumping back to if you’re new to this series and also new to algorithms!), there’s a third basic method of sorting that we have yet to explore: the insertion sort. With the insertion sort, rather than going pair-by-pair and swapping like we did with bubble sort (moving the bigger number to the right) or looking for the shortest doll each time then relocating it to the beginning like we did in selection sort, we focus on sorting each item one by one, moving them in place into a sorted section towards the beginning of our array. This is different from selection sort, because with insertion sort we’re not looking for the smallest number each time. We’re just grabbing the next element, then inserting it into our sorted group where it ought to go. This is perhaps easier to understand with a visualization:

From Wikipedia: https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif

Again, this is pretty similar to how some people might solve sorting problems, and even though it’s also usually pretty slow like Bubble Sort and Selection Sort, if the array is almost sorted it’s actually not a bad option!

Scenario

Let’s take a break from Russian nesting dolls (although boy do I love them) and explore another example that might be more fitting:

Epic lego scene found at: https://boyslife.org/wp-content/uploads/2011/05/lego7.jpg

Let’s say you just finished this badass Lego scene with your kid cousin when your other cousin comes running through the room chasing the cat and accidentally kicks the neatly sorted container of Legos across the floor:

Your cousin (who spent much time sorting them) starts crying and you agree to help re-sort them together. The container that holds the Legos has several compartments that are sized to hold each size of Legos. The compartments go in order of smallest compartment to largest with the smallest compartment for the 1 x 1 Legos to the largest compartment for 2 x 8 Legos at the end. Here are some of the other dimensions of the Legos:

It might make sense for you to sort the loose Legos by just looking at each Lego (one by one) and deciding where it goes in the container. We would consider the container to be our “sorted subset” and the Legos on the floor to be our “unsorted subset.” For each unsorted Lego, we just want to see where it goes in our sorted subset (the container) then insert it. And this is basically how insertion sort works. You build up your sorted subset, inserting unsorted elements into their correct place one by one. You can also probably see why this wouldn’t be awful in the case of just a few Legos. If only a few Legos were dumped, this might be a pretty quick process right? You’d only have to put a few in their place and it would be pretty easy to tell where they go. But if there are lots of Legos, this might take some time (and might not be the best way to go about it).

In pseudocode (i.e. not working code), our sort might look like this:

function insertionSort(arr){
	var unsortedBlock;
    for(var unsortedBlock = 1; unsortedBlock < allBlocks.length; unsortedBlock++){
        unsortedBlock = allblocks[unsortedBlock];
        for(var blockinSorted = unsortedBlock - 1; blockinSorted >= 0 && allBlocks[blockinSorted] > unsortedBlock; blockinSorted--) {
            allBlocks[blockinSorted+1] = allblocks[blockinSorted]
        }
        allBlocks[blockinSorted+1] = unsortedBlock;
    }
    return allBlocks;
}

insertionSort([2,1,9,76,4])

OK so this looks pretty overwhelming. But if we go through it line by line we can see this is a pretty faithful representation of what we just described for the real world insertion source process.

We kick things off by creating our function. It needs to know what we’re sorting and so we feed it the parameter allLegos which represents all of our legos (including sorted and unsorted ones):

function sortLegos(allLegos){

We create a variable for the block we just picked up which we’re trying to sort.

var unsortedBlock;

Next we have a for loop that will allow us to move from one block to the next and sort them. We start at 1 instead of 0 this time because we assume our first block is “sorted.” We can’t exactly compare it to anything else, so until we check it against the next block to see if it’s in the right place, we decide it’s fine where it is. In our for loop, we’ll want to sort all of the unsorted blocks, and this can be represented as the if the “unsortedBlock < allBlocks.length” condition in the middle of our loop. To go from one block to the next, we iterate “unsortedBlock++” which again is the same as saying unsortedBlock = unsortedBlock + 1 or pick up the next unsorted block!

for(var unsortedBlock = 1; unsortedBlock < allBlocks.length; unsortedBlock++){

Next, we’re identifying our unsorted block by where it is in the array (or on the floor in relation to the other Legos).

unsortedBlock = allblocks[unsortedBlock];

Next we have another for loop inside of a for loop, where we compare our unsorted block to see where it fits in to the blocks which have been sorted. To do this, we start by comparing it to the block on the left (unsortedBlock -1). Then we need to look at each of the other blocks to the left and compare it, so we decrement or count down by one each time (blockinSorted–).

  for(var blockinSorted = unsortedBlock - 1; blockinSorted >= 0 && allBlocks[blockinSorted] > unsortedBlock; blockinSorted--) {

Inside our loop, we add our block to where it needs to go:

  allBlocks[blockinSorted+1] = allblocks[blocknSorted]

Then we pick up the next unsorted block and identify it as unsorted (this will be the block to the right of the last sorted block hence the +1).

allBlocks[blockinSorted+1] = unsortedBlock;

Finally, we return our sorted list of blocks (perhaps by putting the container away so it can’t get knocked over again).

  return allBlocks;

If you’d like to learn more about insertion sort including how to implement it in real code, check out the sections below.

Big O Complexity

Worse Case Time Complexity: O(n)^2

Best Case (Nearly Sorted Array): O(n)

Visualizations

Audio-visualization by Timo Bingmann Warning: kinda loud n’ flashy!
Insertion sort vs. bubble sort as illustrated and compared by adorable 3D robots.
Insertion sort as explained with cards. By Computer Science

Pseudocode

1. Start by determining that the first item is sorted. 
2. Pick the second element in the array and compare it to the first. Swap if it's smaller.  
3. Pick the third element in the array, and compare it to the second and first. Insert it where it needs to go. 
4. Pick up the next unsorted element in the array, and repeat the process of inserting it where it needs to go in the sorted portion. 
5. Repeat until everything is sorted. 

Code Examples

Javascript

function insertionSort(arr){
	var currentVal;
    for(var i = 1; i < arr.length; i++){
        currentVal = arr[i];
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

insertionSort([2,1,9,76,4])

Sample Problems

Come back soon for these!

More Resources