Implement Insertion Sort in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach…

Implement Insertion Sort in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!

This article is part of a series covering sort algorithms in JavaScript. You can find the rest of the series here. If you’re new to sorting algorithms, or algorithms in general, read this first to get a solid foundation for moving forward. Today I’ll be covering the ins and outs of insertion sort. Insertion sort is more complex but a little more useful than bubble sort. The worst case scenario for it is similar to bubble sort’s but its best case makes it suited for times when you’re pretty sure a list almost sorted or likely already sorted. Let’s get the big picture.

Insertion sort works by looking at each element within a list (starting with the second element) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next element in the list.

Benefits

Insertion sort isn’t all that bad.. as long as you use it in the right circumstances.

It’s faster than most O(*n *log n) sorting algorithms for small lists.
It’s extremely memory efficient requiring only O(1) auxiliary space for the single item that is being moved.
It’s stable — equal elements appear in the same order in the sorted list.
It’s adaptive — it’s fast when sorting mostly sorted lists or when adding items to an already sorted list.
It’s very easy to implement!

Complexity

The time complexity of this algorithm, at worst case, is quadratic — O(n²). As n approaches infinity the average case approaches the worst case divided by two. However since if your list is sorted or nearly so, it can be O(n) in a best case scenario and thus well adapted to that scenario.

When it’s fast

As mentioned above it can be fast under certain circumstances. Consider the array [6, 7, 8, 9, 5 ], when using an algorithm like merge sort we would still need to split all the items and then merge them back up. With insertion sort we just need to verify that [6, 7, 8, 9] are in the correct ‘sorted so far’ order, then we shift all of them up one index for 1.

Because insertion sort is an adaptive sort, it also makes it an ‘online algorithm’, which means we can start sorting before we get all the items and then merge the lists once the partial sorting has completed.

When Insertion Sort in JavaScript is Useful

Insertion Sort is a valuable sorting algorithm in JavaScript when dealing with small or partially sorted data sets. This algorithm works by iteratively building a sorted portion of the array by inserting each element into its appropriate position. With its time complexity of O(n²), Insertion Sort performs well on small arrays or arrays that are nearly sorted. It offers the advantage of being an in-place sorting algorithm, requiring minimal additional memory. Insertion Sort is also stable, preserving the relative order of equal elements. JavaScript developers can rely on Insertion Sort to efficiently handle sorting tasks on smaller or partially sorted data, ensuring simplicity and effectiveness in their applications.

Pseudocode

Create var and set equal to previous element's index

Loop backwards while index >= 0 and current element > temp var Set next element equal to current element Set next element equal to temp

Code

Next up? Merge sort. One of the most widely used sorting algorithms in browsers today.

JavaScript eBook

I founded Higglo Digital and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a beautifully designed website, check us out.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach…