The Efficiency of Mergesort

Let’s figure out the efficiency of Mergesort. To help with this, we’ll first look at Mergesort from a bird’s-eye view, as this will put everything in perspective.

Here’s a visual that shows the entire Mergesort process in one fell swoop. I removed all of the array data since it’s not relevant to our analysis.

Looking at the diagram, notice that the original array is repeatedly broken down into halves until we’re eventually left with single-element arrays. Note that there are 3 “levels”; that is, for this array of size 8, it takes 3 halvings until we break up the array into single-element subarrays.

In more general terms, when you have an array that is size N, it takes log N halvings until the array is completely broken down into single-element subarrays. This may be more intuitive if you recall our unique definition of log N from Volume 1, Chapter 3. That is, log N is the number of times it takes to halve N until we arrive at 1. In our example, where N is 8, log N is 3, and that’s why we end up with 3 levels in the diagram.

Next, let’s take a look at the order in which the mergesort function is called on each of these subarrays.

There are 15 such calls:

Also of interest is the order in which the merges take place:

When we contrast the two previous diagrams, we see that the order of merges is different than the order of mergesort function calls.

All in all, there are 7 merges. Merges 1, 2, 4, and 5 all take place at Level #3. Merges 3 and 6 operate on all four subarrays at Level #2, and Merge 7 merges the two subarrays of Level #1.

The Time Complexity of Mergesort

Let’s get down to brass tacks. How fast is Mergesort?

To break this down, let’s analyze how many steps take place relative to the N elements of the original array that we’re sorting. Using the “levels” concept we demonstrated in the previous visuals, we find that each level contains N elements, and that we perform merges on all N elements at each level.

The following diagram highlights this point:

So, in our example, where the original array was of size 8, we end up merging 8 elements 3 times. That is, there are 3 levels, and on each level, we merge 8 elements. While it’s true that we perform a different number of merges at each level, it doesn’t change the fact that the number of elements being merged remains the same at each level. That is, we may perform 4 merges at Level #3 and only 2 merges at Level #2, but at both levels, we merge 8 elements.

To generalize this in terms of N, we’d say that we perform merges on N elements multiplied by the number of levels. Given that for N elements there are log N levels, we can conclude that we merge a total of N log N elements since:

N elements * log N levels = N log N merged elements.

Now, Mergesort’s primary operation is to perform merges; it doesn’t do much else. And we’ve already established that merging N elements takes N steps. In other words, a merge takes one step per element being merged. Therefore, since Mergesort merges a total of N log N elements, this means that Mergesort takes N log N steps. In Big O, we’d say that Mergesort takes O(N log N) time.

In truth, I noted earlier that a single-array merge can take about 3N steps when we factor in the extra copying of data (plus the first copying and the comparisons). Accordingly, Mergesort may take 3N log N steps. However, this still reduces down to O(N log N).

Next up, let’s analyze how much memory Mergesort consumes.

The Space Complexity of Mergesort

Mergesort’s memory consumption occurs when the mergesort function makes copies of the array it’s sorting:

Again, the code makes a copy of the array’s left and right halves, which in total takes up the same amount of space as the array itself. Essentially, in addition to the array itself, we have a copy of it as well. Furthermore, these copies aren’t made just once. Each call of mergesort copies whatever array it’s acting upon.

To figure out how much extra space Mergesort takes in total, recall that each call of Mergesort recursively calls itself on the left and right copies after creating them:

Let’s walk through some of the Mergesort steps again and keep track of how many array copies are kept in memory at a given time.

When we first call mergesort on the original array, we create copies of the original array’s left and right halves. The copies are highlighted in the following image:

These copies store an extra N elements in memory, which, in our example, is an additional 8 elements.

We then call mergesort on the left copy, which makes copies of itself:

This means we have to store yet another N/2 elements. That is, N is 8, and we’ve created another 4 elements.

Then, we call mergesort yet again, this time on a copy of a copy:

We create another N/4 elements.

When we unwind the recursion call stack, some of these copies start to disappear, but then new ones are made. For example, if you jump ahead a few steps in the Mergesort algorithm, you’ll see that we have the following set of copies:

So, in this example, we have at most N+(N/2)+(N/4) copied elements at a given time. If we try plugging in different examples of N, we’ll find that this always comes out to be 2N-2 extra elements.

Here are a few examples.

In our example, N is 8, so 2N is 16, and we store an extra 14 elements. This is 2N-2.

If N is 16, we end up with 4 levels of halvings. At a given time, we’ll have N+(N/2)+(N/4)+(N/8) extra elements, which totals 30 elements, which is also 2N-2 (since 2N is 32).

Similarly, if the original array contains 64 values, the total number of extra elements comes out to be 126. Again, this ends up being 2N-2.

Beyond the extra copies, recursion itself takes up additional space since the computer has to keep the call stack in memory. This was discussed in Volume 1, Chapter 19. In our case, this amounts to log N units of memory since we have to keep track of up to log N levels at most. Relative to 2N-2, or even N alone, log N is pretty negligible.

Rounding things off, it emerges that Mergesort takes about 2N extra units of space beyond the original array. When it comes to Big O notation, though, this reduces to O(N).