Mergesort vs. Insertion Sort

When I benchmark Mergesort using the code in for an array of 10 elements, I get these results:

As I’ve said, these numbers aren’t very meaningful until we contrast them with the benchmarking results of a competing algorithm. So, let’s go ahead and benchmark Insertion Sort and compare the two sets of results.

Before we do so, it’s always good to hypothesize as to what the results might be. This way, if we get totally different results, we can more easily notice if something fishy is going on and decide if our experiment isn’t engineered correctly.

You learned in the previous chapter that Mergesort runs in O(N log N) time. And as discussed in Volume 1, Chapter 6, Insertion Sort on average takes O(N²) time. It’s reasonable to hypothesize that Mergesort should be the faster of the two algorithms. With this guesstimate in mind, let’s benchmark Insertion Sort.

Here’s the Insertion Sort code from Volume 1, which I saved in a file called insertion_sort.py:

And here’s the benchmarking code for Insertion Sort:

When I run this code, I get the following results:

Whoa! These results are faster than our Mergesort results. That’s not what I expected at all.

Now, I did run the Mergesort benchmark several minutes ago, and who knows what background processes were running then compared to now. So, I’m going to run both benchmarks again to keep this experiment as controlled as possible. We’ve benchmarked Insertion Sort, so let’s benchmark Mergesort again.

My Mergesort results now are these:

Hmmm, I’m getting similar results as before. So, what’s wrong with my experiment? Why does it seem that Insertion Sort is faster than Mergesort?

Gotcha: Only Using One Data Size

As discussed in Volume 1, Chapter 3, we use Big O notation to measure the trajectory of an algorithm as the data grows. The difference between each category of Big O is, in fact, much more noticeable as the size of the data grows. Take the following diagram:

Here, for example, we compare the trajectories of O(N²) vs. O(N). It’s true that as the data increases, O(N) becomes faster compared with O(N²). However, when we have a small amount of data, as shown on the left side of the graph, the speeds of the two algorithms aren’t all that far apart.

Because of this, when benchmarking two competing algorithms, you also want to run the benchmarks on larger amounts of data. The larger the amount of data, the greater the discrepancy between the two sets of results will be, generally speaking.

When I change the benchmarking code to have both Mergesort and Insertion Sort operate on an array of size 10_000 (instead of 10 as before), I get these results:

That’s a huge difference, and much more in line with our hypothesis. However, a question may still be tugging at your brain.

Benchmarks for the Large and Small

When the array was of size 10, it’s understandable that both Mergesort and Insertion Sort had similar speeds, but why was Insertion Sort faster than Mergesort? Insertion Sort runs at O(N²), which means that it should take about 100 steps. Mergesort, on the other hand, is O(N log N). N is 10, and log N is about 3, so we’re talking about roughly 30 steps.

This gets back to the reason we began benchmarking in the first place. Counting the number of steps is certainly important, but it’s not the only factor that determines an algorithm’s actual-time speed. On the machine-code level, Mergesort’s 30 Python steps have more “overhead” than Insertion Sort’s 100 Python steps.

While I won’t get into the details of how our two sorting algorithms operate on a machine-code level, the following analogy should suffice:

If we asked both an experienced weightlifter and a couch potato to perform 100 pushups, the weightlifter would likely complete them much more quickly than the couch potato. However, knowing the importance of warming up before a workout, the weightlifter might take a few minutes to stretch and do some jumping jacks. Now, even if the couch potato doesn’t do a warmup, the weightlifter will still likely complete all 100 pushups before the couch potato.

However, if we asked each person to do 10 pushups, the couch potato might complete them first since the weightlifter may still insist on warming up before doing any physical activity. By the time the weightlifter finished warming up, the couch potato might already be done (if he’s lucky).

Here as well, Mergesort uses tools such as recursion and copying arrays to perform its powerful work. However, these tools carry a certain amount of overhead that takes some time. Of course, it’s certainly worth using these tools so that Mergesort can sort an array of size 10,000 in O(N log N) time. But when it comes to small arrays, Insertion Sort, which doesn’t have all this overhead, can complete the job quicker than Mergesort despite Insertion Sort being the “slower” algorithm.

Optimizing Mergesort with Insertion Sort

You’ve seen that it’s a mistake not to use large data when benchmarking. However, it’s also a mistake not to use small data when benchmarking.

We learn this lesson from Insertion Sort. Had we never benchmarked Insertion Sort for an array of size 10, we may never have discovered that Insertion Sort is faster than Mergesort for small arrays.

At first glance, this novelty may seem unimportant. After all, we don’t generally care how fast a sorting algorithm works on a small array since even the notoriously slow Bubble Sort algorithm (discussed in Volume 1, Chapter 4) sorts a small array quickly in actual time. However, computer scientists have discovered that we can utilize this attribute of Insertion Sort for the sake of optimizing Mergesort.

To do this, we employ a brilliant little trick: we modify the Mergesort algorithm so that when it encounters an array that has 10 elements or fewer, it switches to Insertion Sort for that array. We’ve never seen one sorting algorithm switch to another midstream, but I assure you that it’s not illegal.

To implement this in our code, we only have to make the tiniest change to our mergesort function. I placed the insertion_sort function inside the same file as my merge and mergesort functions and then swapped out the base case:

Instead of the base case being an array of size 1, the base case is now an array of size less than or equal to 10. When this new base case is encountered, we call insertion_sort on that base-case array.

Let’s now benchmark regular Mergesort against this optimized Insertion Sort-infused version of Mergesort. For an array of size 1_000_000, I get these results:

The optimized version shaves off about one to two seconds from Mergesort’s runtime. With larger amounts of data, this optimization would be even more significant.

In our implementation, we used the number 10 as the tipping point for when Mergesort switches over to Insertion Sort. However, 10 isn’t necessarily the magic number. To determine what the number should be, you could keep benchmarking different numbers until you find the one where Mergesort and Insertion Sort are roughly the same speed. In truth, though, the number may depend on the particular computer you’re using, so there may not be a definitive number.

Another interesting thing to note is that when it comes to small arrays, Insertion Sort isn’t only faster than Mergesort; it’s faster than Quicksort, too. That’s why many finely tuned implementations of Quicksort also switch over to Insertion Sort when it encounters a small array.