| |
A Merge Algorithm | page 4 of 9 |
The mergesort algorithm requires a merge algorithm which we will solve first.
The method header and the specifications of the merge routine are given below. You may assume the array definitions from the sorting template program in Lesson 23 apply.
/* Preconditions: Lists A and B are sorted in nondecreasing
order.
Action: Lists A and B are merged into one list, C.
Postcondition: List C contains all the values from
Lists A and B, in nondecreasing order.
*/
void merge (int A[], int first, int mid, int last)
The merge method breaks down into four cases:
- List
A is done, so pull a value from List B .
- List
B is done, so pull a value from List A .
- Neither is done, and if List A[i] < List B[j] (where i & j are index markers in lists A and B) then pull from List A.
- Neither is done, and if List B[j] <= List A[i] then pull from List B.
It is important to deal with the four cases in the order described above. For example, if you are done with List A (if i > A.length-1 ), you do not want to inspect any values past A[i] .
Example of function Merge:
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
|