The Efficiency of Merging

Let’s analyze how many steps merging takes. If we consider N to be the total number of values of both the left and right arrays combined, then there are at most about 2N steps. Here’s why.

In the previous example, N is 8 because between the left and right arrays, there was a combined total of 8 values. Now, we take N steps to copy each of the N values into the merged array. In addition to the copy steps, we also perform comparison steps when we compare the values at the left and right pointers. In the previous example, we ended up making 6 comparisons. (The final two values of the left array didn’t require a comparison since no comparisons take place during the final phase.) In a worst-case scenario, though, we’d have to make a comparison for all N values save for the last one.

When we add up our N copies and N-1 comparisons, we end up with 2N-1 steps. In terms of Big O notation, this reduces to O(N). As algorithms go, merging is very fast.

Now, here’s a little spoiler regarding Mergesort, the algorithm we’re leading up to. Mergesort itself is considered a very fast sorting algorithm. The reason is that the primary operation that Mergesort performs is merging, and merging itself is a super-fast algorithm, as you’ve seen.

Returning to our analysis of merging, it’s worth noting that merging takes O(N) space. This is because we created a brand-new array and copied all the values into it. We’ll look at the ramifications of this in a little bit.

Merging a Single Array

Imagine you want to sort the following array: [3, 4, 7, 8, 1, 2, 5, 6]. Are there any shortcuts we can take to sort this array?

While contemplating this, do you also notice anything familiar about this array?

If you look closely, you’ll see that while the array as a whole is unsorted, each half of the array on its own is sorted. In fact, this array contains the same values as our prior merging example. We can take incredible advantage of this unique situation to sort the entire array in just O(N) time.

To accomplish this, all we need to do is treat each half of the array as if they were separate arrays, and merge them together! And this will take O(N) time since, as we’ve seen, merging has a time complexity of O(N).

I call this process “single-array merging” (not an official term), and it is the guts of Mergesort, as you’ll soon see. I won’t demonstrate single-array merging since it’s essentially the same process we’ve already walked through.

I refer to this as single-array merging because typically, merging involves two arrays. Here, however, we start with a single array. The merge happens when we split this array into halves and then merge all the data back together again. As we’ve seen, this effectively sorts the array. And again, this only works if the two individual halves already happen to be sorted beforehand.

Tweaking Single-Array Merging

You’ve now seen that single-array merging is a fast way to sort a specific kind of array, namely, one whose two halves are already sorted.

However, we’re now going to make a subtle tweak to single-array merging. In truth, we don’t have to make this tweak, but we’ll do so since the computer science literature does so, for a reason that I’ll explain.

Generally, any given algorithm can come in a number of variants, and Mergesort is no exception. Each algorithm typically has a “classic” version and a number of variants that optimize the algorithm in different ways.

One way to divide a sorting algorithm into two variants is as follows: a sorting algorithm can either sort the original input array, or it can produce a brand-new array that contains all the data in sorted order. Usually, the “classic” version of a sorting algorithm does the former; it sorts the original input array itself.

In this chapter, our focus will be on “classic” Mergesort, which sorts the original array. Because of this, classic Mergesort makes the following tweak to single-array merging.

Instead of dividing the single array and merging the two halves into a brand-new merged array, we’re going to merge the data so that the original array itself gets sorted. As you’ll see momentarily, we’ll accomplish this by first copying the data elsewhere and then merging the data back into the original array.

First, we make copies of each half of the single array, creating two brand-new smaller subarrays:

Then, we merge these two “copies” and put the merged data back into the original array by overwriting all the original values:

In other words, our first version of single-array merging didn’t copy any data before performing the actual merge. We simply merged the two halves of the array into a brand-new array. With this new tweak, however, we first make copies of the two halves and only then merge the data. And in this tweaked version, when we do merge the data, we merge it back into the original array, overwriting its old values.

It’s striking that we have to perform an extra N steps for this “tweaked” merge. That is, in our original version of merging, we spent N steps appending the merged data to a brand-new merged array. However, with our tweak, we first spend N steps copying the data and then another N steps overwriting the original array with the merged data.

So, because our original version takes, at most, 2N-1 steps, this tweaked version takes 3N-1 steps. Luckily, this is still considered fast and is also considered O(N).

Again, the reason for this tweak is somewhat arbitrary; we did it to look at Mergesort in its most classical form before moving on to any of its variants. As I’ve said, the reason why the classical Mergesort algorithm does this is because it can thereby sort the original array, which is what classical sorting algorithms tend to do. The variant of Mergesort that uses our original version of merging, on the other hand, doesn’t sort the original array but instead produces a brand-new array that’s sorted.

Code Implementation: Single-Array Merging

In any case, we’re going to run with this tweaked version of merging. Before we look at all of the code, let’s first focus on the method signature:

We call merge on a single array like the one we had before, namely, [3, 4, 7, 8, 1, 2, 5, 6]. That is, this method is designed to work on an array that has two sorted halves, even though the array as a whole is unsorted. If you’re wondering why such a method is useful, given that such an array is pretty rare, the answer will become clear when I reveal the entire Mergesort algorithm.

To use our method, we’ll pass in the original array, which is the method’s third argument. But, we’ll also first make a copy of each half of the array, and pass those in as the copy_of_left_half and copy_of_right_half arguments. Here’s an example of how we’ll call this method:

It might seem strange that we have to make copies of the left and right halves before calling the merge method. After all, can’t the merge method do that itself? Once it receives the original_array, it should be able to make copies of the two halves. Again, the answer to this will become clear when we reveal the entire Mergesort algorithm. (Don’t worry—we’ll get there soon!)

Now, let’s get to the meat of the merge method. Here’s the complete code:

Let’s walk through this code one piece at a time.

First, we set up our left and right pointers to start at index 0. We also initialize an array_pointer which points to index 0 of the original_array. We’ll need this since we’re going to be overwriting the values of the original_array, and this pointer will point to the index that we’re going to overwrite.

The next bit of code then begins a loop that lasts as long as neither the left_pointer nor the right_pointer has reached the end of their respective arrays.

So, as soon as either pointer reaches the end of its array, this loop will terminate.

We then compare the value at the left_pointer with the value at the right_pointer. If the left_pointer’s value is the lower one (or the two values are equal), the left_pointer’s value gets copied to the original_array at whatever index the array_pointer is at. We also increment the left_pointer by 1:

Note that this overwrites a value from the original_array.

If, on the other hand, the right_pointer’s value is lower, we copy it to the original_array and increment the right_pointer:

In either case, we then increment the array_pointer so it’s ready to overwrite the original_array’s next value:

Once the loop is done, either the copy_of_left_half or copy_of_right_half has at least one value in it that we didn’t yet process. So, we begin the final phase. In the following code, we append the remaining values from the “unfinished” array:

Note that only one of these two conditional statements will be triggered since only one pointer will be past its array.

And that’s all there is to single-array merging!

In a vacuum, sorting a single array using merging seems to be pretty moot. After all, it only works in a very specific case where an array happens to have its two halves perfectly sorted. How often would we encounter such an array? And how would our program even know that it’s dealing with such an array? If only we could somehow ensure that the array we’re sorting is such an array.

Well, reader, we can.