Algorithms: Insertion Sort in JavaScript

A brief look at insertion sort written in JavaScript, including checking the loop invariant and analyzing the run time.

Implementing Insertion Sort

Insertion sort is a very simple algorithm that works best for data that is already mostly sorted. Before getting started, it is always a good idea have a visualization of how the algorithm functions. You can refer to the video at the top of the post to get a sense for how insertion sort works. I recommend using the scrubber to slide through the animation one frame at a time and watch how the indices change.

The basic idea is that we select one element at a time and then search for the correct place to insert it. Hence the name, insertion sort. This results in the array having two parts — the sorted part of the array and the elements that have yet to be sorted. Some like to picture this as two different arrays — one with all of the unsorted elements and a new one that is entirely sorted. However, picturing it as one array is more true to how the code works.

Let’s take a look at the code block and and then discuss it.