Insertion Sort Algorithm 101

A guide to iterative and recursive implementations of the Insertion Sort Algorithm with JavaScript.

Photo by Lewis Ngugi on Unsplash

The Insertion Sort Algorithm (ISA) is another sorting algorithm that sorts a list (or array) of numbers. Unlike divide and conquer algorithms, the ISA scans through an array to find the smallest number and swaps it with the number at the beginning of the list. This process repeats until no more swaps occur and the array has been sorted in ascending order.

Here is an example using a JavaScript array:

For those of you who are still a bit confused take a look at this visual resource from w3resources.com that walks through the whole process.

Sourced from https://www.w3resource.com/javascript-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-

Implementations

Ok, this is where we layout an iterative and recursive implementation of the ISA in JavaScript.

This implementation mimics the visual walkthrough above and loops through an array using 2 iterators that continually look for the smallest number and move it to the beginning of the array. Here is a breakdown the whole function:

  1. The first part is creating 2 loops that scan the unsorted input array. The first loop keeps track of the first element in the array (being scanned). The second loop keeps track of the next element in the array for comparison.

2. Inside the 2nd loop we create a conditional statement comparing the first element in the array to its adjacent element. If the adjacent element is larger than the first element, we swap the elements.

You can replace the swapping sequence inside of the conditional statement with a separate function for the sake of modularity.

The recursive implementation requires a bit more coding, but we can break into 2 functions to keep things clear and easy to understand. With this implementation we actually scan through the array backwards (right to left). Here are the steps to building this out:

  1. We create a swap function to handle the comparison and the in-place swap of the values.

2. Create a recursive function that moves through the array, updating the part of the array that is being scanned and then calling the swap function to compare adjacent elements. Once the len parameter is reduced to 0 and the entire array has been scanned from right to left exit the function.

It’s important to remember that this function sorts the original array in-place and doesn’t actually return anything. So in order to see the sorted result (after the function completes), you can simply console.log() or return the original array.

Conclusion

Hopefully this tutorial laid out how the Insertion Sort Algorithm works and gives you a clear understanding of two common implementations in JavaScript.

As with many tutorials, the explanations don’t always sink in on the first read through. So I definitely recommend taking a look at the actual code on my Github Repo and playing with the implementations yourself. Use console.log() at various points in each function to get a better handle on the order of operations.

For those of you who are curious, the best case time-complexity of an ISA is O(n) and the worst case is O(n⁴). In short, it is not particularly useful in data heavy, high traffic applications.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store