A Merge Algorithm

The mergeSort algorithm requires a merge algorithm that we will design first.

The method header and the specifications of the merge method are given below. You may assume the ArrayList definitions from the sorting template program in Lesson 17 apply.

/* Preconditions: Lists A and B are non-empty and in sorted nondecreasing order.  
Action: Lists A and B are merged into one ArrayList, C.  
Postcondition: List C contains all the values from  
Lists A and B, in nondecreasing order.  
*/  
void merge (ArrayList <Integer> A, ArrayList <Integer> B, ArrayList <Integer> C)

The merge method breaks down into four cases:

1. ArrayList A is done, so pull a value from ArrayList B.

2. ArrayList B is done, so pull a value from ArrayList A.

3. Neither is done, and if A[i] < B[j] (where i & j are index markers in lists A and B) then pull from ArrayList A.

4. Neither is done, and if B[j] <= A[i] then pull from ArrayList B.

It is important to deal with the four cases in the order described above. For example, if you are done with ArrayList A (if i > A.length-1), you do not want to inspect any values past A[i].

Example of method merge results:

See Transparency A18.2, Merging Two Lists

> A: 2 6 11 15 21
> 
> B: 4 5 9 13 17 25 29
> 
> C: 2 4 5 6 9 11 13 15 17 21 25 29