The Efficiency of Insertion Sort

Four types of steps occur in Insertion Sort: removals, comparisons, shifts, and insertions. To analyze the efficiency of Insertion Sort, we need to tally up each of these steps.

First, let’s dig into comparisons. A comparison takes place each time we compare a value to the left of the gap with the temp_value. In a worst-case scenario, where the array is sorted in reverse order, we have to compare every number to the left of temp_value with temp_value in each pass-through. This is because each value to the left of temp_value will always be greater than temp_value, so the pass-through will only end when the gap reaches the left end of the array.

During the first pass-through, in which temp_value is the value at index 1, a maximum of one comparison is made, since there’s only one value to the left of the temp_value. On the second pass-through, the maximum number of comparisons made is two, and so on. On the final pass-through, we need to compare the temp_value with every single value in the array besides temp_value itself. In other words, if there are N elements in the array, the maximum number of comparisons made in the final pass-through is N - 1.

We can, therefore, formulate the total number of comparisons as:

1 + 2 + 3 + … + (N - 1) comparisons.

In our example array that contains five elements, that’s a maximum of:

1 + 2 + 3 + 4 = 10 comparisons.

For an array containing 10 elements, there would be:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 comparisons.

For an array containing 20 elements, there would be a total of 190 comparisons, and so on.

When examining this pattern, it emerges that for an array containing N elements, there are approximately N² / 2 comparisons. (10² / 2 is 50, and 20² / 2 is 200. We’ll look at this pattern more closely in the next chapter.)

Let’s continue analyzing the other types of steps.

Shifts occur each time we move a value one cell to the right. When an array is sorted in reverse order, there will be as many shifts as there are comparisons since every comparison will force us to shift a value to the right.

Let’s add up comparisons and shifts for a worst-case scenario:

N² / 2 comparisons

+ N² / 2 shifts
_____________________________

N² steps

Removing and inserting the temp_value from the array happens once per pass-through. Since there are always N - 1 pass-throughs, we can conclude that there are N - 1 removals and N - 1 insertions.

So now we’ve got:

N² comparisons and shifts combined

N - 1 removals

+ N - 1 insertions
_____________________________

N² + 2N - 2 steps

You’ve already learned one major rule of Big O: that Big O ignores constants. With this rule in mind, we’d—at first glance—simplify this to O(N² + N).

However, I’ll now reveal another major rule of Big O:

Big O notation only takes into account the highest order of N when we have multiple orders added together.

In other words, if we have an algorithm that takes N⁴ + N³ + N² + N steps, we only consider N⁴ to be significant—and just call it O(N⁴). Why is this?

Look at the following table:

As N increases, N⁴ becomes so much more significant than any other order of N that the smaller orders are considered trivial. For example, when looking at the bottom row of the table, when we add N⁴ + N³ + N² + N, we get a total of 101,010,100. But we may as well round that down to 100,000,000, which is accomplished by ignoring those lower orders of N.

We can apply this same concept to Insertion Sort. Even though we’ve already simplified Insertion Sort down to N² + N steps, we simplify the expression further by throwing out the lower order, reducing it to O(N²).

It emerges that in a worst-case scenario, Insertion Sort has the same time complexity as Bubble Sort and Selection Sort. They’re all O(N²).

I noted in the previous chapter that although Bubble Sort and Selection Sort are both O(N²), Selection Sort is faster because Selection Sort has N² / 2 steps compared with Bubble Sort’s N² steps. At first glance, then, we’d say that Insertion Sort is as slow as Bubble Sort, since it too takes about N² steps.

If I stop the book here, you’d walk away thinking that Selection Sort is the best choice out of the three, since it’s twice as fast as either Bubble Sort or Insertion Sort. But it’s actually not that simple.