Learn

Let’s consider how much work this algorithm does in order to sort the array. What do we mean by work? Let’s count how many operations this algorithm does! We’ll consider any time we compare two numbers to be one operation.

This algorithm makes a lot of comparisons using our two `for` loops! Given our sample data `[7, 2, 5, 8, -3]` on our first pass, we are going to make one comparison.

`2` will be compared to `7`. `2` is smaller than `7` so we will shift `7` to the right to make space to insert `2`. `2` is now in the correct position!

On our second pass, we will compare `5` with `7`. `5` is smaller than `7` so we will shift `7` to the right. `5` is not less than `2` so we will not shift over `2` and will insert `5` before `7` where we created space. We made two comparisons.

On our third pass, we will compare `8` with `7`. `8` is not smaller than `7` so we will not shift over any values. We will leave `8` where it is and consider it part of the sorted sub-list. We only made one comparison but could have made up to three if our current element was smaller than any elements in the sorted sub-list.

On our final pass, we will compare `-3` to `8`. `-3` is less than `8` so we will shift `8` over. We will next compare `-3` to `7` and shift `7` over. Next, we will compare `-3` to `5`, and shift `5` over. Finally, we will compare `-3` to `2`. `-3` is less than `2` so we will shift `2` over. This was 4 comparisons.

We made 1 comparison on our first pass, 2 comparisons on our second pass, 1 comparison on our third pass, and then finally 4 comparisons on our last pass for a total of 8 comparisons. For some of those iterations (like the third one) we got lucky! We didn’t have to do too much work to find the correct place to insert the value. However, in the worst-case scenario, we would need to make 10 total comparisons to completely sort all 5 items in the list.

Imagine the number of comparisons we would need to make with ten pieces of data `[7, 2, 5, 8, -3, 12, 6, 80, 7, -70]`. If we were unlucky and in the worst-case scenario, our last pass would make 9 total comparisons. Now, imagine a thousand pieces of data! As the size of the dataset (`n`) gets very big, it turns out that in the worst-case scenario, we need to make n^2 comparisons. In general, if you see an algorithm with a nested for loop, like this one, the algorithm is probably has a runtime of at least O(n^2), if not worse!

Insertion sort does have an interesting best-case scenario where an array is already sorted. Insertion sort has a best-case complexity of `O(n)`. Consider the case when the array is already sorted. We still need to insert every card in our hand into its proper place. But every time we check to see where that card should go, we immediately find the correct place. We need to do `1` comparison for each card, giving us a total of `n` work.