Beginning Java Data Structures and Algorithms

Merging the Problem

How do you merge two sorted lists into a sorted one? This is the task of the merge() function, which is found at the end of the pseudocode shown in the preceding section. This process is shown in Figure 2.4. Merging two sorted lists is an easier task than sorting from scratch.

This is similar to the intersection problem we saw in Chapter 1, Algorithms and Complexities.

We can merge in linear time utilizing just two pointers and an empty array as shown in the following diagram:

Figure 2.4: Before and after merging two sorted arrays

Since the two parts of the split array are both sorted, it's easy to merge the two together. ...