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:

let array = [2,1,4,3];
1. Is the number at index 1 [1] < than the number at index 0 [2]
2. Yes, swap those numbers
3. [1,2,4,3]
4. Is the number at index 2 [4] < than the number at index 0 [1]
5. No
6. Is the number at index 3 [3] < than the number at index 0 [1]
7. No
8. Restart the algorithm from index 1 [2]
9. [..., 2,4,3]
10. Repeat this process for each element in the array until the   whole array is sorted.
11. [1,2,3,4]

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.

Implementations

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

Iterative

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.

const insertionSort = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      
       // more code...
    }
  }
};

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.

const insertionSort = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] > array[j]) {
        let temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
  }
  return array;
};

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

Recursive

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.

const swap = (array, position, value) => {
  // The i iterator tracks the index of the element 
  // immediately  adjacent (to the left) of the value
  let i = position - 1;
  // While i has not run the full length of the array 
  // AND the value at i is greater than the current value
  // Re-assign the element on the right with the element 
  // on the left and decrement i so we move further 
  // (to the left) down the array
  while ((i >= 0) && (array[i] > value)) {
    array[i + 1] = array[i]
    i--
  };
  // Re-assign the element on the right with the value param
  // because it is smaller than the value at array[i]
  array[i + 1] = value;
};

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.

const recursiveInsertionSort = (array, len) => {
  // len must always be the size of the array
  if (len === undefined) {
    len = array.length - 1;
  }
  // Base case, exit the function once we have scanned 
  // the whole array and len === 0
  if (len <= 0) {
    return;
  }
  // This recursive call constantly updates the value of n 
  // to move backwards through the array
  recursiveInsertionSort(array, len - 1);
  // This call makes swaps with the updated index length 
  // and the value at the end of the array
  swap(array, len, array[len]);
};

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.

Here are some excellent resources to help you solidify your knowledge of the Insertion Sort Algorithm:

My Insertion Sort Algorithm Repo —

https://github.com/twjsanderson/insertSortAlgo

A Great Article on Insertion Sort by Kyle Jensen —

Javascript Algorithms — Insertion Sort

An Excellent Article on Insertion Sort in Python —

Selection Sort Algorithm | Interview Cake