A Common-Sense Guide to Data Structures and Algorithms

The Average Case

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

Why?

By definition, the cases that occur most frequently are average scenarios. The worst- and best-case scenarios happen only rarely. Let’s look at this simple bell curve:

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

And this makes a lot of sense. Think of a randomly sorted array. What are the odds that the values will occur in perfect ascending or descending order? It’s ...