Javascript Algorithms — Insertion Sort

In the first post of the Javascript Algorithms series, I will focus on insertion sort. Insertion sort is a very simple comparison sort used for sorting an array (or list). A comparison sort is any sorting algorithm that compares the current value that you are trying to place with other values within the same array/list that’s being sorted. It does this by working with one item at a time, and iteratively places each item into the right order in the array. Comparison sorting algorithms only work where a “less-than” relation is defined (e.g. 2 is less than 5, 3 is not less than 1, alpha is less than beta because a comes before b).

Before we dive into the specifics regarding the implementation of insertion sort, let’s talk more about it’s benefits. Insertion sort runs in O(n²), or quadratic, time in the worst case. This typically isn’t very effective and should not be used for large lists. Because of insertion sort’s low hidden constant value, however, it usually outperforms more advanced algorithms such as quick sort or merge sort on smaller lists. Some implementations of those advanced algorithms will even switch from using their more advanced methodology to insertion sort when the list gets small enough. In practice, insertion sort is also usually more efficient than other quadratic sorting algorithms such as bubble sort or selection sort. It’s best case run time is O(n), or linear, which occurs if the input array is already sorted. On average, insertion sort’s run time is still quadratic.

Some other benefits of insertion sort are that it’s stable, it sorts your list in-place, and that it’s adaptive. A stable sorting algorithm is any algorithm that won’t change the relative order of items in a list that have the same value. Because insertion sort sorts your list in-place, it only uses O(1) (constant) space. This is an example of a time-space tradeoff, where you’re sacrificing the speed of your algorithm in order to conserve memory. Insertion sort is also adaptive, which means that it works well with arrays that are already partially or fully sorted, which reduces it’s run time to O(nk) where each element in the list is no more than k elements away from it’s sorted position.

Now that we’ve covered the benefits of insertion sort, let’s dive into how we would implement it using Javascript (this implementation doesn’t rely on any built-in JS capabilities that other languages don’t have, so it can easily be translated into the language of your choice). Insertion sort works by moving from left to right over an input list. You could compare it to the way you would sort a set of cards that you were holding in your hand. You’d scan the set from left to right, grabbing each card as you go and moving it to the position where the card to it’s left would be smaller or equal to the current card’s value. After you move the card furthest to the right, you’ll be left with a set of cards that has been sorted in ascending order. Insertion sort will use the current item as a “key”, and then search through the items to the left of that item in the input list for the place that the key should go. This means that the sub-list to the left of the current “key” will already be sorted, and will remain sorted after every iteration of insertion sort. Here’s an example: given the array [5,3,1,4,6] we can use insertion sort to sort the array in ascending order.

You can skip the first item (index 0), since any array of size 1 is trivially sorted. Starting with the element at index 1, in this case 3, insertion sort will look at the sub-array to the left of index 1 (which is our current “key”) for the position where the key should be placed. Because 5 is greater than 3, it knows that 3 should be placed before 5. After the first iteration of insertion sort, our array will look like this: [3,5,1,4,6] and our new key will be at index 2 which holds the value of 1. This process will repeat until the last value is compared and sorted, and then insertion sort will return the sorted array.

Iteration 0 (unsorted array): [5,3,1,4,6]

Iteration 1, key is 3 (was at index 1): [5,3,1,4,6] →[3,5,1,4,6]

Iteration 2, key is 1 (was at index 2): [3,5,1,4,6] →[1,3,5,4,6]

Iteration 3, key is 4 (was at index 3, ): [1,3,5,4,6] → [1,3,4,5,6]

Iteration 4, key is 6 (was at index 4): [1,3,4,5,6] → [1,3,4,5,6] — because 6 was already in the right place, no changes are made and insertion sort returns the sorted array. Notice how after each step, all the items to the left of the key are already sorted.

Now for the code:

let insertionSort = (inputArr) => {
    let length = inputArr.length;
    for (let i = 1; i < length; i++) {
        let key = inputArr[i];
        let j = i - 1;
        while (j >= 0 && inputArr[j] > key) {
            inputArr[j + 1] = inputArr[j];
            j = j - 1;
        }
        inputArr[j + 1] = key;
    }
    return inputArr;
};

And that’s all there is to insertion sort! We start the for loop at 1 because in the first step, the sub-array only contains the value at index 0 and has a length of 1, so that sub-array is trivially already sorted. We add the key to inputArr[j + 1] because inputArr[j] would correspond to the first item in the sub-array whose value is less than (or equal to) the key’s value, so we want to place the key immediately to the right of that item. Feel free to copy and paste that code into your browsers console to see how it works! You can also add some console.log statements in the while loop to see how the array looks after each iteration as it’s being sorted. Thanks for reading!