-
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:
-
ArrayList A is done, so pull a value from ArrayList B.
-
ArrayList B is done, so pull a value from ArrayList A.
-
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.
-
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:
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
