Insertion Sort Algorithm 101

Photo by Lewis Ngugi on Unsplash
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]
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.

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...
}
}
};
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;
};

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;
};
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]);
};

Conclusion

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

--

--

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