Comparing Mergesort and Quicksort: Lessons Learned

We now arrive at a pivotal question. Which sorting algorithm is better, Mergesort or Quicksort? Quicksort was the fastest sorting algorithm we covered in Volume 1, but let’s look at how Mergesort measures up to it. (To follow this discussion, you don’t need to remember all the nitty-gritty details of Quicksort; I’ll remind you of the pertinent facts.)

As discussed in Volume 1, Quicksort has an average speed of O(N log N). Now, given that Mergesort also runs, on average, in O(N log N) time, it would seem at first glance that the two algorithms are equally fast. In reality, though, Quicksort is faster than Mergesort in what I call actual time.

I use the term actual time to refer to time as measured in minutes and seconds, and not Big O Notation. A major theme of this volume is that although time complexity can be measured in terms of Big O and counting steps, we shouldn’t ignore the classic definition of time completely.

So, Quicksort and Mergesort have the same time complexity in terms of Big O. However, in actual time, the reality is that for the same N elements, Quicksort takes fewer seconds to run than Mergesort does.

Why is this so?

Not All Steps Are Created Equal

One potential explanation for why Quicksort is faster than Mergesort in actual time is that while Mergesort is O(N log N) in terms of Big O notation, we saw earlier that it takes about 3N log N steps. If we look back at our analysis of Quicksort in Volume 1, we find that Quicksort takes closer to N log N steps.

However, this answer isn’t so simple. First, while our implementation of Mergesort earlier took 3N log N steps, there are other variants that take closer to 2N log N steps.

On the flip side, while Quicksort seems to take just N log N steps, that’s only limited to a best-case scenario where the pivot value keeps ending up smack in the middle of the array. However, in more typical cases, computer scientists have found that Quicksort generally takes closer to 2N log N steps.

So, now we have a real puzzle. If the fastest variants of Mergesort and Quicksort both take around 2N log N steps in average scenarios, why is Quicksort faster? To make things even more puzzling, computer scientists report that the most efficient variants of Quicksort are from two to three times faster than the most efficient variants of Mergesort!

This brings us to our first major lesson, which is going to stir things up.

We see that even when two algorithms take the same number of steps, one algorithm can still be significantly faster than the other in actual time.

In other words, not only can two algorithms have the same Big O but different speeds in actual time, but even if the two algorithms have the same number of steps, one algorithm may still get the job done more quickly.

This can be true for a variety of reasons. One reason has something to do with a concept called spatial locality. We’ll explore this idea further in Chapter 4.

However, let’s focus on another particular reason for now.

What we consider a single “step” in a high-level language like Python may consist of numerous steps in the lower-level processes of the computer. A computer breaks high-level code down into low-level code, generally called machine code, and one step in Python might involve 10 steps of machine code.

Because of this, different types of Python steps can have varying speeds. For example, it’s possible that a Python step that compares two values will create three machine-code commands, while a step of swapping two values may involve 10 machine-code commands.

Exploring Bytecode

To give you a taste of what I’m talking about, let’s take a look at how a simple Python step breaks down into multiple steps closer to the machine level.

In truth, Python doesn’t translate directly into machine code. Rather, the Python code first gets converted to something called bytecode. Bytecode is code that is lower-level than Python, but higher-level than machine code. What’s cool is that it’s super easy to see the bytecode created by our Python code.

Let’s create a file called byte_code_example.py and insert the following Python code:

It’s pretty reasonable to say that this code represents two Python steps.

You can see the bytecode generated by the Python code by running the following command in your console:

This spits out bytecode, which for me looks something like this:

Each line here represents a bytecode step. It shows that our two Python steps trigger eight bytecode steps. Intriguing! (It can be fun to go a little crazy and explore the bytecode of all the Python code we write.)

So, this is one plausible reason as to why Quicksort is faster than Mergesort despite the fact that they involve a similar number of steps. Quicksort might break down into fewer bytecode or machine-code steps than Mergesort does.

Note that even if Algorithm A translates to 10 bytecode steps and Algorithm B translates to 20 bytecode steps, this is no guarantee that Algorithm A will run faster than Algorithm B. It may give us a hint as to the speed of our code, but it will not give us definitive results. However, it’s one factor to consider.

The Limits of Big O Notation

Well, isn’t that a monkey wrench? We already knew that Big O notation had some limitations. For example, we know from Volume 1, Chapter 5, that two algorithms can be classified as O(N) even though Algorithm A takes N steps and Algorithm B takes 10N steps. But now you’ve learned that even when two algorithms take the same number of Python steps, one algorithm can still be significantly faster than the other!

This being the case, how are we supposed to ever truly know which algorithms are the most efficient? In truth, even if we were experts in machine code and spatial locality, it’s still hard to predict the effects of these factors.

The surprising answer to these questions is that, indeed, Big O notation is limited! It’s a framework that allows us to approximate relative speeds of competing algorithms, but it’s far from foolproof. The closer that two algorithms are in terms of the number of steps, the harder it becomes to know which algorithm is faster in actual time.

But there’s good news.

There are more precise tools than Big O out there. One such tool, called benchmarking, is the subject of the next chapter. If Big O is a butter knife, then benchmarking is a scalpel.

This isn’t to say that we’ll be throwing out Big O. Far from it! Big O notation still remains a fundamental tool for conceptualizing algorithm efficiency and grouping algorithms into different general categories. So, we’ll still be using Big O throughout this book extensively. After all, you wouldn’t use a scalpel to butter your bagel.

Trade-Offs

Let’s get back to the issue at hand. Which algorithm is better: Quicksort or Mergesort?

We’ve seen that Quicksort is indeed faster than Mergesort in actual time.

Now, not only is Quicksort faster than Mergesort, but Quicksort also consumes less space than Mergesort. This is because Quicksort doesn’t make any copies of the original array, and the only extra space consumed is the recursion call stack, which is all of O(log N). Mergesort, on the other hand, takes up O(N) extra space, as I explained earlier.

However, it could be argued that Mergesort has one advantage over Quicksort: Mergesort is faster than Quicksort in a worst-case scenario. (In Chapter 3, we’re going to pull the rug out from under this advantage, but we’ll run with it for now.)

So, here’s the deal. In average scenarios, both Quicksort and Mergesort run in O(N log N) time. However, Quicksort has a potential Achilles’ heel: there are cases where it slows down to O(N²) time. Specifically, if an array is already completely or mostly sorted, Quicksort will take about N² steps. You can look back at Volume 1, Chapter 13, where we discussed the reason for this, but for now, you can take my word for it.

On the other hand, Mergesort always runs in O(N log N) time. Essentially, there is no worst-case scenario for Mergesort, as all scenarios get processed at the same speed. If you walk through the steps of Mergesort for any array, you can see for yourself that it will always break down the array in log N levels and will always merge N elements at each level.

So, when choosing whether to use Quicksort or Mergesort, there are pros and cons on each side. On one hand, it may be worth using Quicksort because of its average-case efficiency, even though you may risk encountering a presorted array and having a slowdown. Alternatively, it may be worth it to choose Mergesort and guarantee that your speed is never slower than O(N log N), even though, on average, Mergesort will be slower and consume more memory.

Ultimately, there is no right choice. Only you can decide, based on your software requirements, which choice is better for you. And this is the idea of a trade-off.

We’re certainly no strangers to trade-offs, as we’ve encountered this a number of times throughout Volume 1. One example is the trade-off between time and space discussed in Volume 1, Chapter 19. If Algorithm “A” is faster but consumes more memory, and Algorithm “B” is slower but consumes less memory, which do we choose? Again, it’s a trade-off, and only you can decide which is best for your particular situation.

In truth, almost every technology decision involves a question of trade-offs, and this is certainly so when it comes to data structures and algorithms. I’m placing a special emphasis on trade-offs here because trade-offs will be another major theme of this volume.

We’re not done analyzing the trade-offs of Mergesort and Quicksort yet. We’ve certainly discussed some of the major factors at play, but there’s more analysis to come in the following chapters.