Algorithms 101: JavaScript Insertion Sort and It’s Big O Notation

Considered a simple sorting algorithm, insertion sort is not without its merits. While not as efficient as more advanced algorithms when scaled, it is a stable algorithm in that it does not change the relative order of elements with equal values. It is also an excellent choice when you have to continually add new data as it is received. This is because it only needs to do one pass to determine proper placement and on smaller or mostly sorted arrays or lists, this algorithm will actually outperform some of the more complex algorithms.

How It Works

Insertion sort iterates through an array or list evaluating each element against those that came before it, rearranging as necessary to ensure proper index placement based on those evaluations. This is akin to how someone would sort cards in their hand while playing a card game.

So, how does that actually work?

Let’s say you have an unsorted array of eight elements.

Merge sort compares the first two elements rearranging as necessary to create a sorted sub-section. The algorithm then continues iterating through the array, comparing each element to its predecessor. If the element is smaller in value, comparisons continue against previous elements, moving those elements up one index…