JavaScript Algorithms: Insertion Sort
If you haven’t already done so, I strongly encourage you to read my post on Select Sort first as this post builds upon the principles discussed therein 😊
Insertion Sort is different from Bubble Sort and Select Sort in that there is no swapping. Instead, items are shifted around until a spot can be found to insert another item.
Here’s how it works. Say you have a list…
[ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ]… and you want to sort if from 1 to 10. Insertion Sort assumes the beginning part of the list is sorted then finds a place in the beginning part to insert another item. Each time it adds an item, the beginning/sorted part of the list grows larger until the entire list is sorted. So using the above list, at the start of the process we would assume the sorted part of the list consist of 10 and an empty slot ([ 10, _ ]). The empty slot is because 1 was set aside while we try to find a spot to put it. The process for finding a spot looks like this:
SEARCHING FOR A SPOT TO INSERT 1...
[ 10, _ ]
1 is smaller than 10.
Shift 10 to the RIGHT
---------
[ _, 10 ]
No remaining items to compare with.
---------
Insert 1 in open spot.
SORTED:
[ 1, 10 ]
UNSORTED:
[ 9, 2, 8, 3, 7, 4, 6, 5 ] Pretty simple right? If you look under UNSORTED, you’ll notice 9 is next up to be sorted. How do we do that? Just like this:
SEARCHING FOR A SPOT TO INSERT 9...
[ 1, 10, _ ]
9 is smaller than 10.
Shift 10 to the RIGHT
---------
[ 1, _, 10 ]
9 is LARGER than 1.
Keep 1 at current position.
---------
Insert 9 in open spot.
SORTED:
[ 1, 9, 10 ]
UNSORTED:
[ 2, 8, 3, 7, 4, 6, 5 ] Rinse and repeat a whole bunch of more times…
SEARCHING FOR A SPOT TO INSERT 2...
[ 1, 9, 10, _ ]
2 is smaller than 10.
Shift 10 to the RIGHT
---------
[ 1, 9, _, 10 ]
2 is smaller than 9.
Shift 9 to the RIGHT
---------
[ 1, _, 9, 10 ]
2 is LARGER than 1.
Keep 1 at current position.
---------
Insert 2 in open spot.
SORTED:
[ 1, 2, 9, 10 ]
UNSORTED:
[ 8, 3, 7, 4, 6, 5 ] -------------------------------------------SEARCHING FOR A SPOT TO INSERT 8...
[ 1, 2, 9, 10, _ ]
8 is smaller than 10.
Shift 10 to the RIGHT
---------
[ 1, 2, 9, _, 10 ]
8 is smaller than 9.
Shift 9 to the RIGHT
---------
[ 1, 2, _, 9, 10 ]
8 is LARGER than 2.
Keep 2 at current position.
---------
Insert 8 in open spot.
SORTED:
[ 1, 2, 8, 9, 10 ]
UNSORTED:
[ 3, 7, 4, 6, 5 ] -------------------------------------------SEARCHING FOR A SPOT TO INSERT 3...
[ 1, 2, 8, 9, 10, _ ]
3 is smaller than 10.
Shift 10 to the RIGHT
---------
[ 1, 2, 8, 9, _, 10 ]
3 is smaller than 9.
Shift 9 to the RIGHT
---------
[ 1, 2, 8, _, 9, 10 ]
3 is smaller than 8.
Shift 8 to the RIGHT
---------
[ 1, 2, _, 8, 9, 10 ]
3 is LARGER than 2.
Keep 2 at current position.
---------
Insert 3 in open spot.
SORTED:
[ 1, 2, 3, 8, 9, 10 ]
UNSORTED:
[ 7, 4, 6, 5 ] -------------------------------------------SEARCHING FOR A SPOT TO INSERT 7...
[ 1, 2, 3, 8, 9, 10, _ ]
7 is smaller than 10.
Shift 10 to the RIGHT
---------
[ 1, 2, 3, 8, 9, _, 10 ]
7 is smaller than 9.
Shift 9 to the RIGHT
---------
[ 1, 2, 3, 8, _, 9, 10 ]
7 is smaller than 8.
Shift 8 to the RIGHT
---------
[ 1, 2, 3, _, 8, 9, 10 ]
7 is LARGER than 3.
Keep 3 at current position.
---------
Insert 7 in open spot.
SORTED:
[ 1, 2, 3, 7, 8, 9, 10 ]
UNSORTED:
[ 4, 6, 5 ] -------------------------------------------SEARCHING FOR A SPOT TO INSERT 4...
[ 1, 2, 3, 7, 8, 9, 10, _ ]
4 is smaller than 10.
Shift 10 to the RIGHT
---------
[ 1, 2, 3, 7, 8, 9, _, 10 ]
4 is smaller than 9.
Shift 9 to the RIGHT
---------
[ 1, 2, 3, 7, 8, _, 9, 10 ]
4 is smaller than 8.
Shift 8 to the RIGHT
---------
[ 1, 2, 3, 7, _, 8, 9, 10 ]
4 is smaller than 7.
Shift 7 to the RIGHT
---------
[ 1, 2, 3, _, 7, 8, 9, 10 ]
4 is LARGER than 3.
Keep 3 at current position.
---------
Insert 4 in open spot.
SORTED:
[ 1, 2, 3, 4, 7, 8, 9, 10 ]
UNSORTED:
[ 6, 5 ] -------------------------------------------SEARCHING FOR A SPOT TO INSERT 6...
[ 1, 2, 3, 4, 7, 8, 9, 10, _ ]
6 is smaller than 10.
Shift 10 to the RIGHT
---------
[ 1, 2, 3, 4, 7, 8, 9, _, 10 ]
6 is smaller than 9.
Shift 9 to the RIGHT
---------
[ 1, 2, 3, 4, 7, 8, _, 9, 10 ]
6 is smaller than 8.
Shift 8 to the RIGHT
---------
[ 1, 2, 3, 4, 7, _, 8, 9, 10 ]
6 is smaller than 7.
Shift 7 to the RIGHT
---------
[ 1, 2, 3, 4, _, 7, 8, 9, 10 ]
6 is LARGER than 4.
Keep 4 at current position.
---------
Insert 6 in open spot.
SORTED:
[ 1, 2, 3, 4, 6, 7, 8, 9, 10 ]
UNSORTED:
[ 5 ] -------------------------------------------SEARCHING FOR A SPOT TO INSERT 5...
[ 1, 2, 3, 4, 6, 7, 8, 9, 10, _ ]
5 is smaller than 10.
Shift 10 to the RIGHT
---------
[ 1, 2, 3, 4, 6, 7, 8, 9, _, 10 ]
5 is smaller than 9.
Shift 9 to the RIGHT
---------
[ 1, 2, 3, 4, 6, 7, 8, _, 9, 10 ]
5 is smaller than 8.
Shift 8 to the RIGHT
---------
[ 1, 2, 3, 4, 6, 7, _, 8, 9, 10 ]
5 is smaller than 7.
Shift 7 to the RIGHT
---------
[ 1, 2, 3, 4, 6, _, 7, 8, 9, 10 ]
5 is smaller than 6.
Shift 6 to the RIGHT
---------
[ 1, 2, 3, 4, _, 6, 7, 8, 9, 10 ]
5 is LARGER than 4.
Keep 4 at current position.
---------
Insert 5 in open spot.
SORTED:
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
UNSORTED:
[]
And it’s sorted!
Get Tim Nelson’s stories in your inbox
Join Medium for free to get updates from this writer.
Let’s do it in JavaScript!
As with Bubble Sort and Select Sort, Insertion Sort uses two nested for loops. The main difference is the inner for loop operates in reverse and only concerns itself with shifting items in the sorted part of the loop until a spot is found to put the item in question. Let’s write the function in pieces so it’s we can break it down as we go:
Step 1: Define the function:
const insertionSort = (array) => {
// stuff will go here
}Step 2: Add the outer loop:
const insertionSort = (array) => {
for (let i = 1; i < array.length; i++) {
const curItem = array[i];
// more stuff will go here
}
}Have iteration start at 1 (let i = 1). Set curItem to the item you want to insert in the ordered part of the list.
Step 3: Define the inner for loop (for (var x = i — 1; x >= 0 && array[x] > curItem; x—- )):
const insertionSort = (array) => {
for (let i = 1; i < array.length; i++) {
const curItem = array[i];
for (var x = i - 1; x >= 0 && array[x] > curItem; x--) {
// even more stuff will go here
}
}
}Let’s take a look at what’s going on here.
var x = i — 1;We initializexatiminus one (the sorted portion of the list). Also notice we usevarinstead oflet. More on that latter.x >= 0 && array[x] > curItem;The condition for exiting the loop is somewhat complex.x >= 0: ifxis equal to or less than zero, we exit.array[x] > curItem: ifarray[x]is greater thancurItem(the item we’re trying to find a place to insert), we exit.x—-At the end of each loop, we decrementx. So this means we’ll be moving backwards.
Taken as a whole you can read this like this:
Start at the end of the sorted portion of the list and iterate backwards until we get to the beginning of the list or encounter a value which is higher than the item we’re trying to find a place to insert.
Step 4: Shift the item at index x one place to the right:
const insertionSort = (array) => {
for (let i = 1; i < array.length; i++) {
const curItem = array[i];
for (var x = i - 1; x >= 0 && array[x] > curItem; x--) {
array[x + 1] = array[x];
}
// we'll do something here next
}
}We can be sure it’s safe to shift the the item because we know as long as we’re inside the inner for loop we’re meeting the condition that curItem is smaller than the item currently being iterated (the item at index x). Why are we shifting larger items to the right? Well, if you remember from the example, we’re trying to find a spot to put curItem and shifting is the method we use to make space for that item.
Step 5: Insert curItem in the correct spot:
const insertionSort = (array) => {
for (let i = 1; i < array.length; i++) {
const curItem = array[i];
for (var x = i - 1; x >= 0 && array[x] > curItem; x--) {
array[x + 1] = array[x];
}
array[x + 1] = curItem;
}
return array;
}Since the inner for loop decrements at the end of each iteration then checks for an exit condition at the beginning of each loop, we know that array[x] either doesn’t exist (because array[x + 1] is the first item in the array) or is smaller than curItem and, therefore, array[x + 1] is the “empty” spot — the spot where the item to the left is less than curItem and the item to the right is greater than curItem. Sound like the place we should put curItem, right?
One more thing of note: Remember when I told you to notice we used var x = i — 1 instead of let x = i — 1? Well, the reason for doing this has to do with a key difference between var and let. When we use var, we can define it pretty much anywhere inside the function (unless it’s in a closure or a nested function) and access that value anywhere else within the function. This is called function scope. With let however, things work differently. Variables defined using let only have scope within whichever code block they are define. This is called block scope. If we were to use let instead of var, we wouldn’t have access to x outside of the inner for loop, and that is why we used var instead. There a not a lot of reasons to use var anymore, but this is one of the few and it serves as a good opportunity to learn more about JavaScript scope.
Solution
So I already gave the solution, but here it is again in color (and with parameter validation)!





