Merging in Action

The following diagram represents the arrays we want to merge. Note that the left and right pointers point to the beginning of each of their respective arrays. The merged array starts out as empty:

Now, let’s walk through the process of merging them. Each of our “steps” will consist of two parts. Part A appends a value to the merged array, while Part B consists of moving either the left or right pointer.

Step 1A: First, we compare the left pointer’s value to the right pointer’s value. We take whichever value is lower and append it to the array. In this case, the 1 is lower, so we append the 1:

Step 1B: Because we appended a value of the right pointer, we now increment the right pointer so that it points to the next value of the right array:

Step 2A: We compare the left pointer’s 3 with the right pointer’s 2. Because 2 is lower than 3, we append the 2 to the merged array:

Step 2B: Since we once again appended a value belonging to the right pointer, we move the right pointer another notch rightward:

To expedite the remainder of this walkthrough, I’m only going to show visuals for the appends, that is, Part A of each step. I’ll still mention the pointer movements (Part B), but won’t show them in a dedicated diagram.

Step 3: We compare the values of the two pointers. The 3 is lower, so we append it to the merged array:

Accordingly, we’ll move the left pointer along.

Step 4: We compare the 4 with the 5. We append the 4 to the merged array because it’s lower:

This means we’ll also increment the left pointer again.

Step 5: We now compare the 7 with the 5. The right pointer’s 5 is lower, so that’s the value we add to the merged array:

At this point, we’ll move the right pointer one notch rightward.

Step 6: Next, we compare the 7 with the 6. We copy the 6 to the merged array:

The 6 came from the right pointer, so we move that pointer another notch to the right.

Step 7: This is a noteworthy step because the right pointer has now moved beyond the end of the right array. This means we no longer need to perform any comparisons since we’ve exhausted all the values from the right array.

This triggers the final phase of the merge algorithm, in which we simply take all the values of the remaining array (in this case, the left array) and append each one to the merged array. So let’s go ahead and append the 7 to the merged array:

Step 8: Similarly, we append the 8 to the merged array:

The merge algorithm is now complete! The merged array contains all the values from the left and right arrays, and is also sorted.