Explanation of insertion sort

Most people intuitively try to order items in ascending order this way. Let’s see how.

How do we sort?

Imagine that we need to order some numbers randomly written in a line from smallest to greatest.

Say that these numbers are the following: 5, 3, 10, 4 and 7.

What most people intuitively do is that they start to look at the numbers from the left and if they find a number that is less than those before, they will look for the correct position of the current number.

The first two numbers are 5 and 3. 3, which is at the second position is smaller than 5, therefore we need to move 3 to the left, so the order of the numbers are now 3, 5, 10, 4, 7.

The first two numbers are in the right order, let’s move on to the third one (10). 10 is greater than both 3 and 5, so the order of the first three numbers (3, 5, 10) is already correct.

The fourth number is 4. Unfortunately it’s smaller than the third one (10), so we definitely need to shift it to the left, hence we get 3, 5, 4, 10 for the first four numbers. But that’s still not good, since 4 is greater than 5 and because it’s on the right of 5, we will need to move 4 further to the left. This way the order of the first four numbers will become correct (3, 4, 5, 10).

Let’s incorporate the 5th number (7) as well and find its position compared to the first four numbers. 7 is smaller than 10 (the fourth number in the line), so we need to shift it to the left. The numbers are now 3, 4, 5, 7 and 10. If we quickly compare 7 to the number on its left (5), we will see that 7 is at the right position as it’s greater than 5. We don’t have worry about the rest of the numbers on the left as they are already sorted. We are done, all numbers are correct order.

Description of the algorithm

Let’s inspect the algorithm in general. Say that we have n numbers and call our current number (the one we want to put in the right position) x. We compare x to the ones on its left until we find a number that is smaller than x or we get to the start of the line. When we find such a number (or get to the start of the line), we will insert x in that position and will shift all other numbers to the right by one.

We need to repeat this process with each number and eventually we will get a nicely sorted set of numbers.

It seems to be a good idea to include the numbers we want to sort in an array. x is always the current number and sooner or later each number has to be the current one as we need to inspect each element, which means that we need to iterate over the array and compare each element to the ones on their left. This implies that we will need another iteration: We should to loop over the elements to the left of the current number (x) in order to determine its correct position relative to the numbers on its left.

As we keep moving to the right number by number, the order of the numbers to the left of the current number will always be correct (we have already sorted them in the previous iterations) and our job at each iteration is to find the right position for the current number among the already ordered numbers on the left. Eventually we will get to the rightmost (n_th) number and will find that the rest of the numbers on the left (_n - 1 numbers) have been already sorted. We need to find the correct position for the n_th number, so we iterate over the _n - 1 numbers of the left and find the first number smaller than the _n_th one.

I know that it might sound a bit confusing but once it clicks, it will be very logical to you.

JavaScript code

Let’s move on to the code. I will show one possible solution and will then go over the code line by line.

Our function is called - you can guess - insertionSort and we also have the numbers array:

const numbers = [4, 1, 3, 5, 6, 2];

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    arr[j + 1] = current;
  }

  return arr;
}

Yeah, it’s a lots of i-s and j-s but what’s going on here?

We start with a for loop, which always gives us the current number. The iteration starts at the second element of numbers (i = 1) and mark that element (1 in our case) as current.

Now we need to compare current to the number on its left and this is where the second iteration comes in the picture. Our second iteration is a while loop, where j, which also refers to the indexes of numbers, can’t be lower than 0 (since the first element of the array has index 0). The initial value of j will be the index of the left neighbour of current.

The magic is just about to happen. If the arr[j], which is 4 in our case, is greater than the current number (1), we shift 4 to the right by one. The arr[j + 1] = arr[j] assignment does exactly that. At this very moment we have the following numbers in the array: 4, 4, 3, 5, 6, 2.

Where is 1? It’s stored in current and will get back to it a bit later.

While still inside the while statement, we decrease the value of j by one on each iteration, in this case j will be -1.

The while loop won’t continue because j >= 0 won’t fulfil, so we move on to the last part of the code, where the arr[j + 1] = current assignment happens. Here we add back that 1 to j, hence arr[j + 1] will be the first element of the array (index 0) and we make this element equal to current, where we initially stored the value of 1. This is how 1 returns to the array. The order of the numbers after this step is [1, 4, 3, 5, 6, 2].

The for loop continues with the next element, i = 2 on this iteration. current will be 3, the third element (index 2) of numbers and j is initially 1. Let’s have a look at the most difficult part of the code, which is the while loop.

Since j >= 0 and arr[1] (which is 4 now) is greater than current (3), both conditions are met, so the statements inside the while block will execute.

arr[j + 1] = arr[j] assigns the third element (index 2 as j equals 1) of numbers the value of arr[1] (4), so we shift 4 to the right again. The numbers at this moment are 1, 4, 4, 5, 6, 2, the missing number 3 is stored in current. Let’s decrease j by 1, so it will become 0. Back to the condition of the while loop: j >= 0 is met but arr[j] > current is not as arr[0] equals 1 and current is 3.

So we jump to the statement after the while block. arr[j + 1] will refer to arr[1] as the value of j is 0 at the moment, so we assing the stored value of 3 (current) to the second element (arr[1]) of numbers. After this step our array is the following: [1, 3, 4, 5, 6, 2].

Almost there! The next two elements, 5 and 6 are in the correct position compared to the numbers on the left (1, 3, and 4), so the second condition of the while statement (arr[j] > current) won’t be met. arr[j + 1] = current will leave the numbers unchanged as it simply adds 1 back to j, so it simply neutralizes the effect of subtracting 1 at the j = i - 1 step.

We arrive at the last value of numbers, which is 2. This will be the value of current and j will initially be 4.

The conditions of the while loop are both met (4 >= 0 and arr[6], which is 6 is greater than 2). Again, we shift 6 to the right by one, so it will go to its final, last position. The order of the numbers will be 1, 3, 4, 5, 6, 6 now. After decreasing j by 1, arr[j] will refer to the index 3 element (5), which is also greater than current (2), so we shift 5 to the right by one as well, therefore we will get 1, 3, 4, 5, 5 and 6.

We keep shifting numbers greater than 2 to the right until we get to the first number that is less than 2. This will be the first element of the array (1, j will be 0 here). At this very moment the numbers will be in the order of 1, 3, 3, 4, 5, 6. The conditions of the while loop are not met anymore, so we make the final correction and make arr[j + 1] (i.e. the second element as j is 0) equal to the stored value of current and finally our numbers are in ascending order.

As a last step we return arr in which the numbers are correctly ordered.

Considerations

As I mentioned above, insertion sort is not the most efficient sorting algorithm. It contains two iterations and iterations are expensive.

The best case scenario is when the numbers are already ordered. This time we simply iterate over the numbers (for loop) and the conditions of the while loop will never be met as the elements are already in the right order. We have to iterate over the numbers once, so the time the function needs to run for only depends on the number of the elements in the array.

On the contrary, when the numbers are in reverse order (worst case), both the for loop (it will always run no matter what the order of the numbers is) and the while loop will run every time. This time we need to deal with nested iterations with one loop being inside the other and nesting will make insertion sort an expensive algorithm. It’s true though that the probability of having the numbers in reverse order is quite small (1 / 720) and in most cases the while loop won’t run on every for iteration as the example above proves.

A more detailed analysis of insertion sort in terms of time complexity will be covered in a later post.

Conclusion

Insertion sort is the most natural way of sorting elements in ascending order. Unfortunately, it’s not the most efficient sorting algorithm, for example quicksort is faster most of the time.

The code itself is not easy to digest in my opinion and it takes some time to understand. This is not the only correct solution though. I challenge the reader to find another valid insertion sort solution but the code might be longer or more difficult than the one above.

I hope that this post could help you understand insertion sort. If so, see you next time.