# Inching Towards Insertion Sort

### Vaidehi Joshi ăť13 min read

Most of the algorithms that weâve been dealing with have been pretty slow, and seem inefficient. However, they tend to come up a lot in computer science courses and theoretical explanations because they are often used as the naive approach, or the simplest implementation of sorting a collection.

Todayâs sorting algorithm is no different. In fact, some people think that this methodology of sorting is one of the most intuitive. Weâre going to take a look at *insertion sort*, which you might already be familiar with, and may have used at some point in your life already. The interesting thing about insertion sort is that while it is not the most efficient, it always introduced in CS textbooks and lectures.

So why isÂ this?

Well, this stems from the fact that insertion sort is one of the easier sorting algorithms to understand. In fact, the example that comes up quite often is sorting a hand of cardsĂ˘âŹĹ âĂ˘âŹĹ you may not have even realized it, but the last time that you had a bunch of playing cards in your hand, there is a good chance that you were implementing some version of the insertion sort algorithm to sort the cards in yourÂ hand!

Letâs inch a little closer to this algorithm, and figure out what itâs allÂ about.

### Inspecting insertion sort

On a very basic level, an ** insertion sort algorithm** contains the logic of shifting around and inserting elements in order to sort an unordered list of any size. The way that it goes about inserting elements, however, is what makes insertion sort so very interesting!

An insertion sort algorithm has two main aspects to it. Itâs first important aspect has to do with how itâs structured.

The insertion sort algorithm maintains two subsets (often referred to as subsections or sublists)Ă˘âŹĹ âĂ˘âŹĹ a

sortedsubset, and anunsortedÂ subset.

The second aspect has to do with how it iterates and sorts the collection of elements that it is given. Insertion sort will iterate through the unsorted subset, effectively âremovingâ it from the unsorted subset and subsequently âinsertingâ it into its correct, sorted spot in the sortedÂ subset.

Letâs take a look at how this actuallyÂ works:

In the example above, we start off with an unsorted collection. We can think of this as our hand of cards, which is currently in a big, jumbled mess and needs to be sorted. Weâll take the first element and start sorting based on that element. In other words, our first item is the first one that we âsortâ. This now gives us two distinct collections: a sorted collection, and an unsorted collection.

Then, weâll remove the first unsorted element, and add it to our sorted collection. In order to figure out *where* to put this new element, weâll need to compare it to the single item in our sorted collection; if the item that weâre adding is larger than our single, sorted element, weâll keep it at the same place that it is currently at, and mark it as sorted. However, in this example, the new element is smaller than our single, sorted element, weâll move that item back to the first position in the collection, and shift the sorted element forward in the collection to make room forÂ it.

That makes for a single iteration of insertion sort. Obviously, the list still isnât sorted though! Weâd need to continue this process for every single remaining unsorted element, and repeat the same steps as we finish iterating through theÂ list.

In some ways, insertion sort is similar to another algorithm that we have already explored: selection sort. Both of these algorithms have one thing in common: they each maintain a concept of âsortedâ elements and âunsortedâ elements. However, they each do this in very different ways. This is much more clear with anÂ example.

Letâs try our hand at using insertion sort to sort through a list of six numbers: 4, -31, 0, 99, 83,Â 1.

To start, our list will be unsorted. We already know that the first item is going to be moved over to our âsortedâ subset, which means that, initially, only the number 4 isÂ sorted.

To make it a little easier to see, weâll use a red dividing line in this example to indicate the border between the sorted and unsorted collections.

Next, weâll pull out the first *unsorted* element: -31. We want to add it to our sorted subset, so weâll need to compare it to all the sorted items (we only have one right now, though!). Since -31 is smaller than 4, weâll shift 4 into the next spot in the list, and move -31 into the spot that the number 4 was originally in.

Our sorted list now contains -31 and 4, in the correct, sorted order, as we would expect. Weâll do the same thing again, for the next unsorted element, 0. Weâll remove it from the sorted list, compare it to each of the sorted values, and move any elements that are larger in size to the right, in order to make room for the new element beingÂ added.

Effectively, once our first item is pulled out into the âsortedâ subset, we continue the same process for every single unsorted item in the âunsortedâ subset, until we have sorted the entire collection.

### A deeper insertion sort inspection

Before we get into implementing insertion sort, itâll be helpful to try and simplify it a bit to make it a little easier to actually write in code. Weâll can boil down this algorithm into to basicÂ rules.

First, we must remember that whatever element is at index 0 to start off with will be our âsortedâ subsetĂ˘âŹĹ âĂ˘âŹĹ at least, initially. A helpful rule of thumb to remember is that if we only ever have one element, by definition, that element is considered *sorted*; this starts to make more sense if you think about it. If you only have one element, thereâs no chance of anything being larger or smaller than it, so itâs sorted byÂ default!

Second, as we iterate and expand through our âunsortedâ subset, weâre slowly shifting over elements into our sorted subset with each iteration. This means one iteration shrinks the âunsortedâ subset by removing and element and adding it to the âsortedâÂ subset.

In other words, each iteration of insertion sort causes the sorted subset to grow, and the unsorted subset toÂ shrink.

This might not make a ton of sense just yet, and thatâs okay. In fact, I think itâll be a whole lot easier to identify how this works and see it in action if we look at a quick visualization of insertion sort:

In the example above, one row represents the state of the inputted collection for each iteration of the sorting algorithm. Hopefully, itâs a bit more evident whatâs going on here. In each iteration, one more element is considered âsortedâ, which is indicated by the red squares. We can see that, with every iteration, there are more red, âsortedâ elements, and fewer purple, âunsortedâ elements. The number of items isnât changing, of courseĂ˘âŹĹ âĂ˘âŹĹ weâre just moving over a single unsorted element in each iteration, and adding it to the âsortedâ subset. Notice the direction in which this flow is happening, too. Weâll come back to that in the next section, but you might already be able to see a pattern emergingÂ here!

Okay, now that we have the two important rules under our belt, letâs get to the good stuff and actually write some code! Below is an adapted version of insertion sort in JavaScript, based on Rosetta Stoneâs JS implementation. Hereâs what our insertionSort algorithm might look like:

```
function insertionSort(array) {
// Traverse through length of array, starting with the element at index 0.
for (var i = 0; i < array.length; i++) {
// Our current place in the unsorted portion of the array.
// currentUnsortedItem is the item we will be moving into the "sorted" subset of our array.
var currentUnsortedItem = array[i];
console.log('currentUnsortedItem is currently ' + currentUnsortedItem);
// Iterate through sorted items.
// If the current unsorted item is smaller than the item to its left,
// move the current item back one position in the array.
// This loop will never run for the very first unsorted item at index 0.
for (var j = i; j > 0 && currentUnsortedItem < array[j - 1]; j--) {
console.log(currentUnsortedItem + ' < ' + array[j-1] + ' is ' + (currentUnsortedItem < array[j - 1]));
// Shift item left in the sorted subset of the array.
array[j] = array[j - 1];
console.log('** inserting ' + array[j - 1] + ' at index ' + j);
}
// Shift item to the right in the sorted subset fo the array.
array[j] = currentUnsortedItem;
console.log('** inserting ' + currentUnsortedItem + ' at index ' + j);
console.log('array is now: ' + array);
}
return array;
}
```

Weâll notice almost immediately that there are two loops going on here, which is something that weâve seen a few times before. But before we examine thatâŚwhat *else* is going onÂ here?

Well, we start off by traversing through the array input, and adding the first item at index 0 to the âsortedâ portion of the list; this happens on line 6, when we set var currentUnsortedItem = array[i];. This actually doesnât change what the array *looks* like, it just creates our âsortedâ section and an âunsortedâ section. Another thing to note is that, for the first element/iteration, we never actually execute the nested loop on lineÂ 13.

But what about on future iterations? The easiest way to see how that nested loop works (and when it executes) is by running the code. So letâs do exactly that! Hereâs what our insertionSort algorithm would look like with an input of [4, -31, 0, 99, 83,Â 1]:

```
> var a = [4, -31, 0, 99, 83, 1];
> insertionSort(a);
> currentUnsortedItem is currently 4
> ** inserting 4 at index 0
> array is now: 4,-31,0,99,83,1
> currentUnsortedItem is currently -31
> -31 < 4 is true
> ** inserting 4 at index 1
> ** inserting -31 at index 0
> array is now: -31,4,0,99,83,1
> currentUnsortedItem is currently 0
> 0 < 4 is true
> ** inserting 4 at index 2
> ** inserting 0 at index 1
> array is now: -31,0,4,99,83,1
> currentUnsortedItem is currently 99
> ** inserting 99 at index 3
> array is now: -31,0,4,99,83,1
> currentUnsortedItem is currently 83
> 83 < 99 is true
> ** inserting 99 at index 4
> ** inserting 83 at index 3
> array is now: -31,0,4,83,99,1
> currentUnsortedItem is currently 1
> 1 < 99 is true
> ** inserting 99 at index 5
> 1 < 83 is true
> ** inserting 83 at index 4
> 1 < 4 is true
> ** inserting 4 at index 3
> ** inserting 1 at index 2
> array is now: -31,0,1,4,83,99
>> (6) [-31, 0, 1, 4, 83, 99]
```

Cool! We can even see all those console.logâs printing out exactly whatâs going on in the algorithm, which is super helpful. Seeing the code implementation of this hopefully highlights that weâre still taking the exact same steps we were earlier, back when we had only just pseudo-coded insertion sort:

- We iterate through the unsortedÂ items.
- In each iteration, we compare the first unsorted item to each sorted item to its left, which is
*larger inÂ size*. - If the item is larger, we shift over the larger sorted item to the next index location in the array, and we
the unsorted item into the shifted-over itemâs previousÂ index.*insert*

We can also visibly see that, for the first item in this arrayĂ˘âŹĹ âĂ˘âŹĹ in this case, the number 4Ă˘âŹĹ âĂ˘âŹĹ we never iterate through the sorted items, and there are no console.logâs from the inner for loop (just as we expected!).

Hereâs my question, though: compared to our recent code implementation of bubble sort, the executed code here for insertion sort doesnât seem *that* bad. Sure, there are a good number of comparisons being made here, but it doesnât seem as terrible as bubble sort was. So what makes this algorithm slow? Why, exactly, is it inefficient?

Time to findÂ out!

### Working out insertion inefficiency

Since this isnât our first algorithm rodeo, hopefully when you saw those two nested loops, you immediately knew that was bad news for our algorithmâs running time. From our experiences with bubble sort last week and selection sort the week before that, we already know that this makes for ** quadratic** running time, or

**, in Big O notation.**

*O(nĂÂ˛)*Quadratic running time generally a bad idea, because it means as our input doubles, the time it will take for our insertion algorithm to sort our input will *quadruple*. This does not bode well for us if we have a large dataset that weâre trying toÂ sort.

However, itâs still worth looking at why those two nested loops are necessary. And, when it comes to insertion sort, these two loops are particularly interesting, because they function in a really rather uniqueÂ way.

If we look at the example show here, we can see that there are two loops being visualized: an outer loop, and an innerÂ loop.

The outer loop is where we do our iterating through the unsorted listĂ˘âŹĹ âĂ˘âŹĹ every single element is going to be iterated through in this loop, and weâll iterate from left to right, starting with the first unsorted element on the left, which eventually becomes the first sortedÂ element.

The inner loop represents the âshifting overâ of elements. This is where we iterate through the *sorted* elements; this is where we compare an unsorted element to the sorted ones in order to decide where it should live in the âsortedâ subset. However, unlike the outer loop, the inner loop will only run for *n-1* elementsĂ˘âŹĹ âĂ˘âŹĹ where *n* is the total number of elements in the arrayĂ˘âŹĹ âĂ˘âŹĹ since it never executes for the very first element in the list. Another thing that makes the inner loop different from the outer loop is that weâre iterating from right to left, rather that left toÂ right.

This makes sense if we think about it a bit moreĂ˘âŹĹ âĂ˘âŹĹ when we implemented and executed our JavaScript insertionSort, we compared the first unsorted element to the rightmost sorted one. It if it was smaller, we shifted the elements over, and then continued to do the same thing: we compared our unsorted element to the next rightmost sorted one. Effectively, what we were doing was *iterating again*, through the sortedÂ subset.

This double iteration is exactly what makes insertion sort an inefficient algorithm. However, itâs also what makes this sorting algorithm so unique,Â too!

Another really interesting characteristic of this algorithm is that if it is *mostly* sorted, it no longer needs to make as many iterations or comparisons in the nested, internal loop. This means that, even though the worst case running time for insertion sort is O(nĂÂ˛), given an array where the items are almost all sorted, the time complexity for the algorithm changes in a significant way. In fact, the running time actually improves drastically.

The best case running time of running an insertion sort algorithm on a nearly-sorted list ends up being linearĂ˘âŹĹ âĂ˘âŹĹ or, O(n)Ă˘âŹĹ âĂ˘âŹĹ since far fewer comparisons need to be made by the innerÂ loop.

Of course, we donât generally classify or consider algorithms based on their best-case scenarios, but rather by the worst-case. So, despite this interesting fact, we end up bucketing insertion sort as an algorithm with a quadratic runningÂ time.

What other ways can we classify the insertion sort algorithm using the terms that weâre already familiarÂ with?

We already know that insertion sortâs time complexity is ** quadratic** , or O(nĂÂ˛). We also know that it doesnât really require that much extra spaceĂ˘âŹĹ âĂ˘âŹĹ the amount of space it needs within its two nested loops is constant, or O(1), and ends up being used for making temporary variable references to elements at a certain index in the array. Since it operates directly on the inputted data (and doesnât make a copy of it), and needs only a constant amount of memory to run, insertion sort can be classified as an

**sorting algorithm.**

*in-place*When the algorithm iterates through the unsorted elements and inserts them into the correct spot in the âsortedâ subset, it does so by iterating from right to left. This means that, for a collection with multiple values that are the same, they will be placed in the exact same order in the sorted subset as they appeared in the unsorted subset. If we look at the code again, this becomes more evident. Since weâre using comparison operators (such as < and >), if two elements are the same, one wonât be moved in front of the other. Instead, the second duplicate element will simply be inserted to the right, after the first. This makes insertion sort a ** stable** sorting algorithm. Since we also reaffirmed the fact that this algorithm uses comparison operators, we can classify it as a

**algorithm.**

*comparison*Since we know that this algorithm iterates (twice!) we know that it is *iterative*, and hence ** non-recursive** in nature. Finally, since insertion sort maintains all of its data in main memory, and doesnât require any external memory, it can be categorized as an

**.**

*internal sorting algorithm*So, the next time that youâre playing Go Fish with a friend, and find yourself losing horribly, with a whole bunch of cards in your handĂ˘âŹĹ âĂ˘âŹĹ remember the power that is insertion sort. Maybe you can just distract everyone by teaching them this sorting algorithm and emerge the realÂ winner!

### Resources

Insertion sort is fairly common in most computer science courses and curricula, which means that itâs pretty easy to find loads of examples and tutorials explaining how it works. If you feel like taking a deeper dive, stepping through some other examples, or crawling through more code, these links are a good place toÂ start.

- The Insertion Sort, Interactive Python
- Data Structures & Algorithms: Insertion Sort, Tutorials Point
- Sorting algorithms/Insertion sort, RosettaÂ Code
- Insertion Sort, KhanÂ Academy
- Insertion Sort, Professor Rashid BinÂ Muhammad
- Insertion Sort, HarvardÂ CS50

*This post was originally published on medium.com*

Always look forward to these posts. Thanks for breaking it down and providing the additional resources!