Insertion Sort in JavaScript

Introduction

In this article, we will explain what the idea behind Insertion Sort is and implement it in JavaScript.

Insertion Sort is one of the simpler sorting algorithms. It's highly intuitive, stable, in-place, and of comparison-type.

A stable sorting algorithm is an algorithm in which two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

In other words, if a sorting algorithm is stable, equivalent elements retain their relative positions after the sorting algorithm is done.

An in-place algorithm is an algorithm that uses no additional memory or data structures, rewriting the original memory locations of the elements in the input array or list.

Finally, a comparison algorithm is the one that, during its execution, only reads list elements through a single abstract comparison operation. Depending on your data type and goal, the comparison can be done via a relational operator or through a custom comparison function.

Despite it having a very large time complexity for a sorting algorithm, Insertion Sort can be very useful, sometimes even being able to outperform some of the most efficient sorting algorithms, such as Quicksort or Merge Sort, on small collections.

It's rarely used as a standalone algorithm - you'd typically use a fast sorting algorithm like Quicksort and finish up the last "loose ends" with Insertion Sort since it's highly efficient for that task.

Insertion Sort

The idea behind Insertion Sort is often compared to the way people sort a hand of cards while playing Rummy.

In this card game, the dealer deals out cards to each player. Then, the players take the cards given to them one by one, sorting them in their hand in ascending order by inserting each card in its place.

During this entire process, the players hold one sorted pile of cards in their hands, while the unsorted pile from which they draw new cards is in front of them.

A very useful property of Insertion Sort is the fact that it doesn't need to know the entire array in advance in order for it to be sorted - it just inserts the given elements one by one.

This really comes in handy when we want to add more elements in an already sorted array, because Insertion Sort will add the new elements in their proper places without resorting to the entire collection.

Here's a visual representation of how Insertion Sort works:

Insertion Sort Implementation

Now that we understand the idea behind Insertion Sort, we can move on to the implementation:

function insertionSort(inputArr) {
    let n = inputArr.length;
        for (let i = 1; i < n; i++) {
            // Choosing the first element in our unsorted subarray
            let current = inputArr[i];
            // The last element of our sorted subarray
            let j = i-1; 
            while ((j > -1) && (current < inputArr[j])) {
                inputArr[j+1] = inputArr[j];
                j--;
            }
            inputArr[j+1] = current;
        }
    return inputArr;
}

The iteration starts at the second element. We consider the first element sorted by default. For each iteration, we keep track of the current element. Each current element will be the first element of the unsorted array - and each element before it will belong to the sorted array.

Through a while loop, we go through the sorted array and shift elements to the right, opening up a space for the current element to be inserted.

Once we find the proper place for it, the current element is inserted into the newly-opened slot. This process is repeated for each iteration until the array is sorted.

Now, let's populate an array and call our sorting algorithm:

let inputArr = [5, 2, 4, 6, 1, 3];
insertionSort(inputArr);
console.log(inputArr);

The output of this array will be:

(6) [1, 2, 3, 4, 5, 6]

Let's go over this example step-by step:

First Iteration:

Sorted array: 5
Unsorted array: 2, 4, 6, 1, 3

• The first element in our unsorted array is 2.
• 2 < 5, so we move 5 one place to the right.

Sorted array: _, 5

• 2 is placed in its right spot.

Second Iteration:

Sorted array: 2, 5
Unsorted array: 4, 6, 1, 3

• The first element in our unsorted array is 4.
• 4 < 5, so we move 5 one place to the right.

Sorted array: 2, _, 5

• 4 !< 2, so we don't move 2.
• 4 is placed in its right spot.

Third Iteration:

Sorted array: 2, 4, 5
Unsorted array: 6, 1, 3

• The first element in our unsorted array is 6.
• 6 !< 5, so we don't move 5.

Sorted array: 2, 4, 5

• 6 is placed in its right spot.

This is repeated until we're greeted with a sorted array: 1, 2, 3, 4, 5, 6.

We can notice an invariant in each of these iterations. For the k-th iteration of our loop, the interval of [0,k] is guaranteed to be sorted.

Time Comparison

The best running time of Insertion Sort is linear, and we get it if our input array is already sorted. This means that Insertion Sort works wonders when it comes to checking whether or not the array is sorted.

However, the worst and average time complexity is O(n²), which is pretty bad for a sorting algorithm, especially when it is applied to arrays or lists of a bigger size. In this case, Quicksort or Merge Sort with a complexity of O(nlogn) would be a much better choice.

On the other hand, being one of the fastest quadratic sorting algorithms, Insertion Sort usually outperforms Bubble Sort, Gnome Sort and Selection Sort. In addition to that, when our input array size is very small (10-20 elements), Insertion Sort can even outperform Quicksort and Merge Sort.

This is why JavaScript, despite using Quicksort (in Chrome) or Merge Sort (in Mozilla) as the primary sorting algorithm, also uses Insertion Sort on small collections - and after Quicksort/Merge Sort has done the bulk of the work.

Conclusion

Insertion Sort is a simple, stable, in-place, comparison sorting algorithm.

Despite being pretty time-consuming with quadratic complexity, it is very useful when the input array is small in size. In this case, it even outperforms the most commonly used divide-and-conquer algorithms, which is why JavaScript uses a combination of Insertion Sort and Merge Sort or Quicksort when using built-in sorting functions.

When it comes to larger-sized arrays, it outperforms most other quadratic sorting algorithms, including Bubble Sort, Gnome Sort, as well as Selection Sort.