After talking a bit about Bubble Sort and Selection Sort we will mention yet another simple JavaScript Sorting Algorithm - Insertion Sort.
🔷🔷

Introduction

In our JavaScript Sorting Algorithms series we are explaining and implementing different sorting algorithms using JavaScript. The next Javascript sorting algorithm that we'll talk about is Insertion Sort.

Insertion Sort is considered an 'elementary' sorting algorithm, like the last two we wrote about (check the navigation), but compared to them it is actually somewhat useful and good to know outside the standard interview environment. The sorting algorithm divides the array into two portions. One portion is 'sorted', and the algorithm gradually fills out that portion with new values.

So, how we implement this algorithm? First, we will create a one-item chunk of the array we want to sort, and then we iterate from the next array in line - and we set each element to the place it belongs in the left portion.

💯 💯

Pseudocode

1. We will start by selecting the second element in the array
2. Afterward, we will compare that element to the element before it and act accordingly (swap if necessary)
3. We will go to the next element, and then we again check where it fits in the sorted left portion of the array
4. The algorithm repeats the logic until the array is sorted
5. Return the array

Visualization

For the visualization, let us use the same inputs as the last time for selection sort: [11, 17, 5, 28, 3, 6, 15].
📊

The first element in our array will fit into the sorted portion, characterized by the color orange. Then we select the next element in line (red) to compare it to the sorted portion. We see that 17 is larger than 11, so it stays in place, but the next element - 5 is smaller than both 11 and 17, and we will rearrange items so that 5 can fit in the correct place (green). And we do this for every element in the array.

Implementation

function insertionSort(arr) {
    for(var i = 1; i < arr.length; i++) {
        var currentVal = arr[i];
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j + 1] = arr[j];
        }

        arr[j + 1] = currentVal;
    }
    return arr;
}

console.log(insertionSort([11, 17, 5, 28, 3, 6, 15]));

As we already mentioned we start from the second element in the array (hence the var i = 1) and we iterate until the end. Inside every loop iteration, we redeclare the currentVal variable as the current value of the index i, and then we iterate backward from that element to the start of the array. For every iteration in which the currentVal is smaller than the value indexed by j we 'move' the element one place forwards until we find the correct spot for the current value!

Big O Complexity

As other elementary sorting algorithms Insertion Sort is also quadratic - O(n²), because as we increase the number of inputs elements we need to quadratically increase the runtime!

Let us mention some benefits to Insertion Sort. If the array is almost sorted we can just compare and move the elements which are out of place. Additionally, insertion sort can work dynamically, meaning that we can feed it new elements in real time - which is not possible by other algorithms.

Conclusion

We will conclude this part of JavaScript Sorting Algorithms with Insertion Sort here! If you liked this one please check the whole series or visit my blog for more tech articles.