The Average Case

Indeed, in a worst-case scenario, Selection Sort is faster than Insertion Sort. However, it’s critical we also take into account the average-case scenario.

Why?

By definition, the cases that occur most frequently are average scenarios. Take a look at this simple bell curve:

Best- and worst-case scenarios happen relatively infrequently. In the real world, average scenarios are what occur most of the time.

Take a randomly sorted array, for example. What are the odds that the values will occur in perfect ascending or descending order? It’s much more likely that the values will be all over the place.

Let’s examine Insertion Sort, then, in the context of all scenarios.

We’ve looked at how Insertion Sort performs in a worst-case scenario—where the array is sorted in descending order. In the worst case, we saw that in each pass-through, we compare and shift every value we encounter. (We calculated this to be a total of N² comparisons and shifts.)

In the best-case scenario, where the data is already sorted in ascending order, we end up making just one comparison per pass-through and not a single shift, since each value is already in its correct place.

Where data is randomly sorted, however, we’ll have pass-throughs in which we compare and shift all of the data, some of the data, or possibly none of the data. If you look at the preceding walk-through example in , you’ll notice that in the first and third pass-throughs, we compare and shift all the data we encounter. In the fourth pass-through, we compare and shift just some of it, and in the second pass-through, we make just one comparison and shift no data at all.

(This variance occurs because some pass-throughs compare all the data to the left of the temp_value, while other pass-throughs end early, due to encountering a value that is less than the temp_value.)

So in the worst-case scenario, we compare and shift all the data, and in the best-case scenario, we shift none of the data (and just make one comparison per pass-through). For the average scenario, we can say that in the aggregate, we probably compare and shift about half the data. Thus, if Insertion Sort takes N² steps for the worst-case scenario, we’d say that it takes about N² / 2 steps for the average scenario. (In terms of Big O, however, both scenarios are O(N²).)

Let’s dive into some specific examples.

The array [1, 2, 3, 4] is already presorted, which is the best case. The worst case for the same data would be [4, 3, 2, 1], and an example of an average case might be [1, 3, 4, 2].

In the worst case ([4, 3, 2, 1]), there are six comparisons and six shifts, for a total of twelve steps. In an average case of [1, 3, 4, 2], there are four comparisons and two shifts, for a total of six steps. In the best case ([1, 2, 3, 4]), there are three comparisons and zero shifts.

We can now see that the performance of Insertion Sort varies greatly based on the scenario. In the worst-case scenario, Insertion Sort takes N² steps. In an average scenario, it takes N² / 2 steps. And in the best-case scenario, it takes about N steps.

You can see these three types of performance in the following graph:

Contrast this with Selection Sort. Selection Sort takes N² / 2 steps in all cases, from worst to average to best-case scenarios. This is because Selection Sort doesn’t have any mechanism for ending a pass-through early at any point. Each pass-through compares every value to the right of the chosen index no matter what.

Here’s a table that compares Selection Sort and Insertion Sort:

So which is better: Selection Sort or Insertion Sort? The answer is, well, it depends. In an average case—where an array is randomly sorted—they perform similarly. If you have reason to assume you’ll be dealing with data that is mostly sorted, Insertion Sort will be a better choice. If you have reason to assume you’ll be dealing with data that is mostly sorted in reverse order, Selection Sort will be faster. If you have no idea what the data will be like, that’s essentially an average case, and both will be equal.