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…