January 22, 2023

Algorithms: Insertion Sort


Let me start this post with a question. Is an array of a single item a sorted array?

Not a trick question! It is, and we use this fact with insertion sort.

In the previous post on bubble sort, our algorithm spent a lot of time comparing items that were already sorted, especially near the end of the sort. That’s really inefficient. How might we be able to avoid making these unnecessary comparisons?

If we were able to track an array that we knew to be sorted, we could stop looping past this array and instead insert items, one by one, into their correct position. Doing so, would save us a few unnecessary comparisons.

To accomplish this, we treat the first item in the array as a sorted list of a single item. Then, we compare the rest of the items to the items in this sorted list. When we find a spot for our item, we insert it into the sorted portion. By the time we finish looping through each item, our list will be sorted. No need for a final loop to verify nothing changed.

The details

The insertion sort algorithm goes like this:

  • Treat the first item as a sorted
  • Thus, starting from the 2nd item in the array, loop through each item
  • For each item:
    • Loop through the sorted portion of our array
    • Compare each item in the sorted portion to the item in the outer loop
    • If the outer item is less than the inner item
      • Remove the outer item from its current position
      • Splice it into the inner position
function insertionSort(items) {
  let i
  let j

   * Loop from the start of the unsorted portion of our array
   * aka the second item
  for (i = 1; i < items.length; i++) {
     * Loop thru the sorted portion of our array
     * aka from the first item to our outer item
    for (j = 0; j < i; j++) {
       * Compare the item at `i` with `j`
      if (items[i] < items[j]) {
         * We can remove the item at `i` out and destructure it
        const [item] = items.splice(i, 1)

         * And splice the item back in at `j`
        items.splice(j, 0, item)

  return items

We can see it in action here:

Comparisons: 0

Take notice that while we still do a lot of comparisons, we do quite a bit fewer than we did with bubble sort. In running the component above a few times in testing, I noticed it was about 1/2 as many as the bubble sort on average. That’s a pretty good improvement. But we can still do better, and we’ll learn how soon.

For egghead subscribers

If you enjoy learning from video content and have an egghead account, you can watch this lesson in the embed below or at https://egghead.io/lessons/javascript-sort-an-array-with-a-nested-for-loop-using-insertion-sort-in-javascript.

Liked the post?
Give the author a dopamine boost with a few "beard strokes". Click the beard up to 50 times to show your appreciation.
Need help with your software problems?

My team and I are ready to help you. Hire Agathist to build your next great project or to improve one of your existing ones.

Get in touch
Kyle Shevlin's face, which is mostly a beard with eyes

Kyle Shevlin is the founder & lead software engineer of Agathist, a software development firm with a mission to build good software with good people.

Good software by good people.
Visit https://agath.ist to learn more
Sign up for my newsletter
Let's chat some more about TypeScript, React, and frontend web development. Unsubscribe at any time.
Logo for Introduction to State Machines and XState
Introduction to State Machines and XState
Check out my courses!
If you enjoy my posts, you might enjoy my courses, too. Click the button to view the course or go to Courses for more information.