May 14, 2021

If you want to think like a programmer, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing common patterns in software development. In this tutorial, you will learn how to code the insertion sort algorithm in JavaScript.

Give yourself an A. Grab your copy of A is for Algorithms

- What is programming?
- What is an algorithm?
- What is computational thinking?

Programming is the act and art of writing instructions to be executed by a machine. These instructions must follow a predetermined, formalized, set of rules. These rules determine what we can write and how we can use those whats. A programming language is, fundamentally, a combination of logic and syntax, or a set of instructions for writing instructions. So meta!

An algorithm is a set of clearly defined rules or instructions to be executed by a computer in order to solve a specific problem.

Computational thinking is an approach to problem solving where we frame our solution in terms that a computer could also execute. Computational thinking consists of the following stages:

**Decomposition**: Breaking a complex problem into smaller, easier to solve components**Pattern recognition**: Developing a generalized solution to apply to multiple problems**Abstraction**: Hiding or ignoring the details of a problem in order to simplify it and make it easier to solve**Algorithms**: Composing step-by-step instructions to solve a problem

- Why is it called ‘Insertion Sort’?
- What Problem(s) Does Insertion Sort Solve?
- What is the Big O of Insertion Sort?

If we are writing a sorting algorithm, we need to start with something to sort. Let’s declare an array of ‘unsorted’ integers:

`const unsorted = [10, 1, 9, 2, 8, 3, 7, 4, 6, 5];`

Next, let’s declare our `insertionSort`

function:

```
const insertionSort = (arr) => {
return arr;
};
```

Now what?

In order to understand our problem, we need to break it down.

Let’s first define it and reframe the problem as acceptance criteria:

GIVEN an array of unsorted numbers

WHEN we check the value of each number and find one out of sequence

THEN we insert that number in its ordinal location in the array

Where have we seen this or something like it before?

Let’s use an analogy!

Imagine you were holding a deck of cards and you wanted to put the cards in order. Usig the first half of our `unsorted`

array as an example gives us the following hand:

`10, 1, 9, 2, 8`

Moving left to right, you would look at the value of the first card and compare it to the value of the second card. In this instance, our first card is `10`

and our second card is `1`

. `10`

is greater than `1`

, so we *swap* their positions. Now our hand looks like this:

`1, 10, 9, 2, 8`

Again, moving left to right, we compare the values of our next two cards and see that `10`

is greater than `9`

, so we take `9`

out of our hand *temporarily* and *insert* it between `1`

and `10`

. Now our hand looks like this:

`1, 9, 10, 2, 8`

And again, moving left to right, our next two cards are `10`

and `2`

. `10`

is greater than `2`

, but, now, `9`

is *also* greater than `2`

, so we *temporarily* remove `2`

from our hand and then *insert* `2`

between `1`

and `9`

. Now our hands looks like this:

`1, 2, 9, 10, 8`

Lastly, we *temporarily* remove `8`

from our hand and compare it to the other cards. `10`

is greater than `8`

, and `9`

is greater than `8`

, but `2`

is not. So we *insert* `8`

between `2`

and `9`

. Our sorted hand looks like this:

`1, 2, 8, 9, 10`

So… how do we translate this to JavaScript?

With our analogy in hand (get it), let’s break down, or *decompose* the problem.

What if our array only contained two values?

`const test = [10, 1];`

We can see that we need to compare our two values, and if the first value is greater than the second value, we need to swap them.

Our immediate inclination might be something like this:

```
const insertionSort = (arr) => {
if (arr[0] > arr[1]) {
arr[1] = arr[0];
arr[0] = arr[1];
}
return arr;
};
```

But this won’t work. Why?

The result will be the following:

`[10, 10]`

We could create a new array and return that, *or*, if we think back to our playing cards analogy, we can *temporarily* remove a value from the array and then *insert* it into the array.

```
const insertionSort = (arr) => {
if (arr[0] > arr[1]) {
arr[1] = arr[0];
arr[0] = arr[1];
}
return arr;
};
```

But which value do we *temporarily* remove? `0`

or `1`

?

Let’s revisit our playing cards analogy again: if we are proceeding left to right through our hand, or array, do we pull the first card or the second?

`const unsorted = [10, 1, 9, 2, 8, 3, 7, 4, 6, 5];`

If we are using the first half of our array, our inclination is likely to *temporarily* remove the first card as it is greater. But what if we are working with the latter half of the array, where the first value is *less than* the next?

`3, 7, 4, 6, 5`

If we *temporarily* remove the first card, `3`

, we would check its value against the next card, `7`

, see that `3`

is less than `7`

, and simply put it back in its original location.

We could also start with `7`

, check its value against the previous card, see that `7`

is greater than `3`

, and return it to its location in our hand.

Do you see the pattern? So what about `10`

and `1`

?

We *could* temporarily remove `10`

and check it against the next value, but as we saw above, we could accomplish the same end by starting with the second card, or value, in this case `1`

.

Long story short, to *temporarily* remove a value from our array, we simply declare a variable `temp`

and assign it the value stored in `arr[1]`

:

```
const insertionSort = (arr) => {
let temp = arr[1];
if (arr[0] > temp) {
arr[1] = arr[0];
arr[0] = temp;
}
return arr;
};
```

Now that we *recognize the pattern*, how do we *abstract*, or model, this?

What do I mean by that?

As soon as we declared `temp`

, we entered the realm of abstraction. `arr[1]`

and `arr[2]`

both refer to specific values in our array. But `temp`

can refer to *any* value we assign to it. In our conditional statement, we are still making specific reference to `arr[0]`

.

What is `arr[0]`

in relation to `arr[1]`

?

It’s the *previous* index in our array, so let’s declare a new variable, `prev`

and assign it a value of 0.

And what is `temp`

in relation to `prev`

?

`prev + 1`

When we refactor our `insertionSort`

function, we only need to make reference to specific value in array, `arr[1]`

. The rest are abstractions.

```
const insertionSort = (arr) => {
let temp = arr[1];
let prev = 0;
if (arr[prev] > temp) {
arr[1] = arr[prev];
arr[prev] = temp;
}
return arr;
};
```

Now it’s time for the last stage of computational thinking: let’s get algorithmic!

Our current solution is great for two values, but how do we sort an array of multiple values?

*For* each value in the array, we need to check it against the previous values and insert it in ordinal sequence…

Let’s refactor our function with iteration. Rather than `i`

, let’s use a descriptive iterator variable, `curr`

, short for *current*, to help us *see* what’s happening.

What value do we assign to `curr`

?

We might be inclined, by force of habit and inertia, to initialize our iterator variable with 0, but let’s recall our card analogy above. We don’t need to start with the first card in our hand when starting with the second card achieves the same end and is more efficient. So… let’s initialize our `for`

loop with 1.

We also need to update our reference to `arr[1]`

with a `arr[curr]`

:

```
const insertionSort = (arr) => {
for (let curr = 1; curr < arr.length; curr++) {
let temp = arr[curr];
let prev = 0;
if (arr[prev] > temp) {
arr[curr] = arr[prev];
arr[prev] = temp;
}
}
return arr;
};
```

What happens when we run our `insertionSort`

function?

`[ 1, 10, 9, 2, 8, 3, 7, 4, 6, 5 ]`

Our first two numbers swapped, but nothing else. Why?

We need to *algorithmically* determine the value of `prev`

. In our conditional statement, we are only comparing each number against the value stored in `arr[0]`

, which, after the first iteration is `1`

.

If `prev`

is the value *previous* to `curr`

, how can we determine it without hard coding a value?

`let prev = curr - 1;`

Our algorithm now looks like this:

```
const insertionSort = (arr) => {
for (let curr = 1; curr < arr.length; curr++) {
let temp = arr[curr];
let prev = curr - 1;
if (arr[prev] > temp) {
arr[curr] = arr[prev];
arr[prev] = temp;
}
}
return arr;
};
```

If we run it, the result is the following:

`[ 1, 9, 2, 8, 3, 7, 4, 6, 5, 10 ]`

What is going on here?

We’re only checking values forward, not back, so for each iteration, `arr[prev]`

is 10, and we swap all of the values with it until we reach the end of the array.

That’s cool if our goal is *just* to sort the largest value.

Let’s visualize this…

Here’s our `unsorted`

array:

`10, 1, 9, 2, 8, 3, 7, 4, 6, 5`

In the first iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

1 | 1 | 0 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 10, 2, 8, 3, 7, 4, 6, 5 ]`

In the second iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

2 | 9 | 1 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 2, 10, 8, 3, 7, 4, 6, 5 ]`

In the third iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

3 | 2 | 2 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 2, 8, 10, 3, 7, 4, 6, 5 ]`

In the fourth iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

4 | 8 | 3 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 2, 8, 3, 10, 7, 4, 6, 5 ]`

In the fifth iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

5 | 3 | 4 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 2, 8, 3, 7, 10, 4, 6, 5 ]`

In the sixth iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

6 | 7 | 5 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 2, 8, 3, 7, 4, 10, 6, 5 ]`

In the seventh iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

7 | 4 | 6 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 2, 8, 3, 7, 4, 6, 10, 5 ]`

In the eighth iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

8 | 6 | 7 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 2, 8, 3, 7, 4, 6, 5, 10 ]`

In the ninth and final iteration, the values stored in our variables are the following:

`curr` |
`arr[curr]` && `temp` |
`prev` |
`arr[prev]` |
---|---|---|---|

9 | 5 | 8 | 10 |

And our `insertionSort`

function returns the following:

`[ 1, 9, 2, 8, 3, 7, 4, 6, 5, 10 ]`

Do you see the pattern?

What’s the solution?

With every iteration *forward*, we need to word backwards and sort the preceding numbers as well.

What control flow statement easily allows us to count down?

`while`

Which of the values listed in our tables above do we want to use as our condition?

`prev`

Why?

Because *abstraction*!

With each iteration of our `while`

loop, we want to check the value stored in the *previous* array index. And with each iteraton of our `for`

loop, we reassign the value of `prev`

to `curr - 1`

.

Let’s refactor our function with a `while`

loop:

```
const insertionSort = (arr) => {
for (let curr = 1; curr < arr.length; curr++) {
let temp = arr[curr];
let prev = curr - 1;
while(prev >=0) {
if (arr[prev] > temp) {
arr[curr] = arr[prev];
arr[prev] = temp;
}
prev = prev - 1;
}
}
return arr;
};
```

NOTE: `prev = prev - 1;`

is *outside* the `if`

statement. If we placed it inside, we would get caught in an endless loop as there are definitely iterations where `arr[prev]`

will be less than `temp`

.

Running `insertionSort`

now returns:

`[ 1, 2, 2, 3, 3, 4, 4, 5, 5, 6 ]`

Well… it’s sorted. But also *shorted*. What’s going on?

When we decrement `prev`

with each iteration of our `while`

loop, it is no longer *coupled* with `curr`

. What is `curr`

, abstractly?

`prev + 1`

Let’s update that in our function…

```
const insertionSort = (arr) => {
for (let curr = 1; curr < arr.length; curr++) {
let temp = arr[curr];
let prev = curr - 1;
while(prev >= 0) {
if (arr[prev] > temp) {
arr[prev + 1] = arr[prev];
arr[prev] = temp;
}
prev = prev - 1;
}
}
return arr;
};
```

Now when we run our `insertionSort`

function, it returns:

```
[
1, 2, 3,
4, 5, 6,
7, 8, 9,
10
]
```

- Why is it called ‘Insertion Sort’?
- What Problem(s) Does Insertion Sort Solve?
- What is the Big O of Insertion Sort?

Insertion Sort gets its name from the approach to sorting where a numerical value is *inserted* into an array in ordinal sequence.

Insertion Sort is useful, and ideal, when the data to be sorted is small or nearly sorted.

What is the Big O of Insertion Sort? Because we are working with nested iteration, it’s O(n^2).

If you want to think like a programmer, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing common patterns in software development. In this tutorial, you will learn the insertion sort algorithm in JavaScript.

Want to level up your problem solving skills? I write a weekly newsletter about programming, problem solving and lifelong learning. Join now