Insertion Sort for Javascript Newbies

Today is all about insertion sort and implementing it in javascript! Insertion sort is, as you may have guessed, a sorting algorithm. It is fairly slow compared to more powerful sorting algorithms like heapsort, mergesort, and quicksort. That doesn’t mean it isn’t worth learning though. I am of the belief that building these things out and making your brain think about these puzzles can only make you a better coder.

If you are new to coding and want to learn some algorithms as a fun way to improve your skills, insertion sort is a great one to start with as the steps are pretty easy to follow along.

Great! So what is it?

Steps

Insertion sort works like this:

1. For each item in a list
2. Compare it to the previous item. If the previous item is larger, swap it.
3. If you have swapped those two, continue swapping the larger element with the ones before it until it is in the right place.

Swapping

Great! So let’s start with some array of jumbled numbers:

What a mess. Someone better sort those numbers.

Okay so let’s look at step 1 again.

For each item in a list

Okay we can do that. That sounds like a for loop to me. There’s also a bit of a clue in step 2 about where to start. Step 2 says, “compare it to the previous item.” That tells me that our for loop is going to start iterating at index 1 and not index 0, because it needs a previous element to compare. Okay let’s get started!

Great. We got the skeleton of our loop! Let’s look at step 2 again:

Compare it to the previous item. If the previous item is larger, swap it.

Okay! Let’s do that.

Woah we are seriously nailing this. Great job everyone. Okay next step!

If you have swapped those two, continue swapping the larger element with the ones before it until it is in the right place.

Hmm… okay. Well. I guess we could write another loop in that if statement? Maybe another for loop that loops backwards starting at index i and goes back to the beginning?

Yes, we could do that. We could do a lot of things. But should we?

To me, this step has some clues as to what we should do. The step is structured as if-something-then-something (it doesn’t say “then” anywhere, but “then” is implicit because English is weird). This sounds like a great base case for a recursive function. If we call a recursive function inside that for loop, it can handle recursively calling itself as needed, saving us the trouble of writing tricky nested loops but achieving the same behavior.

So what does that look like? Well let’s back up and look at those steps again.

1. For each item in a list
2. Compare it to the previous item. If the previous item is larger, swap it.
3. If you have swapped those two, continue swapping the larger element with the ones before it until it is in the right place.

So this code is covering step one:

Now let’s go ahead and build a helper function that takes in an index and an array as its arguments. It will handle the checking and swapping involved in step 2 by comparing the element at the index passed in with the previous element:

Okay. Why did we do this?

Well now, we can make checkAndSwap() recursive, using the if statement on line 8 as our base case, and passing in i — 1 as the index to check. Let’s see that!

So now checkAndSwap() will call itself recursively until the element at the index passed into it is in its right place. So we’ve solved the problem of having to write messy nested loops on line 3. Again, you can do it that way, but I personally have a really hard time reading code like that. I like everything to have an easy flow of logic that I can follow by just reading the code, and nested loops with multiple iterator variables and tons of if statements make my brain hurt.

Okay cool so now we just have to call this function inside of that for loop!

Cool! Now let’s look at our array from the beginning:

Our for loop is going to start by calling checkAndSwap() on arr[1]. It will see that 5 is larger than 3 and do nothing to our array, sending it back to the next iteration of our for loop.

Next our for loop will have i = 2 and will call checkAndSwap() on arr[2]. So now we are comparing 2 and 5 in our array. The if statement on line 8 will evaluate to true and the block of code below will execute, swapping the 5 and the 2 and calling checkAndSwap() again on arr[1]. Before the recursive call happens on line 10, our array looks like this:

2 and 5 swapped places, which is great! But see how 2 isn’t done swapping? It needs to swap with 3 now to be in its proper place. This is why have the recursive call on line 10 in our code!

Let’s take one last look at our steps:

1. For each item in a list
2. Compare it to the previous item. If the previous item is larger, swap it.
3. If you have swapped those two, continue swapping the larger element with the ones before it until it is in the right place.

Looks like we got all those bases covered, right? I guess all that is left is to return our array! This is a very easy step, but one that many newbies get stuck on. When I first started learning javascript, I would spend hours debugging code that was doing exactly what I needed it to, with the exception that I forgot to return something from my function. So remember, always return the thing you need!

A Note on Pure Functions and Return Values

checkAndSwap() does not need to return anything because insertion sort sorts arrays in place, meaning it operates on the original array rather than making a copy that is a sorted version of the array. Since we don’t need a return value from checkAndSwap(), we don’t have to write a return statement.

For those of you following along with programming paradigms in mind, this means that insertion sort does not fit into the functional programming paradigm because it is mutating our original data. A big clue that a function is not pure (i.e. it has the side-effect of mutating our original data) is if it makes sense for the function to not have a return value.

Wrapping Up

I hope you enjoyed learning insertion sort with me! If you want more content like this, check out my posts Heapsort for Javascript Newbies and Beginner Rubyist’s Guide to Quicksort.

Thanks for reading!