Merging Arrays

Mergesort sorts arrays by relying on another more basic algorithm known as merging arrays, or simply merging, for short. In this context, to merge arrays means to take two arrays that are already sorted, copy all of their values into a third array, and end up with the third array also completely sorted. Let’s look at a basic example.

Let’s say we have the arrays [3, 4, 7, 8] and [1, 2, 5, 6]. Note that each array is already sorted. I can’t emphasize this enough: merging arrays only works if the arrays are already sorted.

The goal of merging is to take all of the values from both arrays and copy them into a third array, which will contain all the values in sorted order. The result of merging these two arrays will be: [1, 2, 3, 4, 5, 6, 7, 8].

The following diagram shows the finished product of a merge:

The merging algorithm follows these steps:

1. Initialize a “left pointer” and have it point to the first index of the left array.

2. Initialize a “right pointer” and have it point at the first index of the right array.

3. Create a third, empty array. This will be the “merged” array. By the end, the merged array will contain all the values from the left and right arrays in sorted order.

4. Run a loop until either the left pointer or the right pointer reaches the end of its array. Within the loop, do the following:

   1. Compare the value of the left pointer with the value of the right pointer and determine which value is lower;

   2. Take the lower value and append it to the merged array;

   3. Whichever pointer was pointing to the lower value gets incremented so that it points to the next index of its array. (If at any point the two values we’re comparing are equal, we can arbitrarily append the value of the left array and move its pointer along.)

5. Once the loop is complete, either the left or right array will be “unfinished” in that it will still have values that were not yet copied to the merged array. This triggers the “final phase” of the algorithm.

6. Final phase: take all the remaining values of the “unfinished” array and append them, in order, to the merged array.

Let’s now take a look at the merge algorithm in action, using an example.