Sorting, Searching, and Merging - Advanced Topics in Java: Core Concepts in Data Structures - page 25

else // j == n, copy A[i] to A[m-1] to C
for ( ; i < m; i++) C[++k] = A[i];
return m + n;
} //end merge
The function takes the arguments A , m , B , n , and C , performs the merge, and returns the number of elements,
m + n , in C .
Program P1.8 shows a simple main function that tests the logic of merge . It sets up arrays A and B , calls merge ,
and prints C . When run, the program prints the following:
16 21 25 28 35 40 47 54 61 75
Program P1.8
public class MergeTest {
public static void main(String[] args) {
int[] A = {21, 28, 35, 40, 61, 75}; //size 6
int[] B = {16, 25, 47, 54}; //size 4
int[] C = new int[20]; //enough to hold all the elements
int n = merge(A, 6, B, 4, C);
for (int j = 0; j < n; j++) System.out.printf("%d ", C[j]);
System.out.printf("\n");
} //end main
// merge goes here
} //end class MergeTest
As a matter of interest, we can also implement merge as follows:
public static int merge(int[] A, int m, int[] B, int n, int[] C) {
int i = 0; //i points to the first (smallest) number in A
int j = 0; //j points to the first (smallest) number in B
int k = -1; //k will be incremented before storing a number in C[k]
while (i < m || j < n) {
if (i == m) C[++k] = B[j++];
else if (j == n) C[++k] = A[i++];
else if (A[i] < B[j]) C[++k] = A[i++];
else C[++k] = B[j++];
}
return m + n;
}
The while loop expresses the following logic: as long as there is at least one element to process in either A or B ,
we enter the loop. If we are finished with A ( i == m ), copy an element from B to C . If we are finished with B ( j == n ),
copy an element from A to C . Otherwise, copy the smaller of A[i] and B[j] to C . Each time we copy an element from
an array, we add 1 to the subscript for that array.
While the previous version implements the merge in a straightforward way, it seems reasonable to say that this
version is a bit neater.