Merging sorted arrays of unequal length

Question

I have a project that requires me to merge two, sorted arrays (a and b) and place the result in a new array of length a.length + b.length. I'm tracking both the counter of my placement in all 3 arrays, and the length of my arrays are unequal. My convention is that if one array runs out before another, the code will just dump the rest of the other array into the result array.

Unfortunately, the only way that I can check if the other array still contains elements is seen the for loop.

Can anyone help me? This should a relatively easy fix, but I can't think of a solution.

public class Two {
    public static void main(String[] args) {
        //sample problem
        int[] var_a = {2,3,5,5,8,10,11,17,18,20}; 
        int[] var_b = {5,6,7,8,14,15,17};
        final int a_size = 10;
        final int b_size = 7;
        final int c_size = 17; 
        int[] var_c = new int[17];

        int aCount = 0;
        int bCount = 0;
        int cCount = 0;
        for (cCount = 0; cCount < c_size; cCount++) {
            //b runs out before a runs out
            if ((bCount == b_size) && (aCount <= a_size)) {
                //dump rest of var_a into var_c     
                var_c[cCount] = var_a[aCount];
                aCount++;
            }
            //PROBLEM: bCount is equal to bSize, and is triggering the break.
            //a runs out before b runs out
            else if ((aCount == a_size) && (bCount <= b_size)) {
                //dump rest of var_b into var_c
                var_c[cCount] = var_b[bCount];
                bCount++;
            }

            if ((aCount >= a_size) || (bCount >= b_size) || (cCount >= c_size)) {break;}

            if (var_a[aCount] < var_b[bCount]) {
                var_c[cCount] = var_a[aCount];
                aCount++;
            } else if (var_a[aCount] > var_b[bCount]) {
                var_c[cCount] = var_b[bCount];
                bCount++;
            } else if (var_a[aCount] == var_b[bCount]) {
                var_c[cCount] = var_a[aCount];
                aCount++;
                cCount++;
                var_c[cCount] = var_b[bCount];
                bCount++;
            }
        }
        for (int i : var_c) {
            System.out.print(i + " ");
        }
    }
}

Answer 1

A common solution to this issue is replacing a single loop with three:

• First loop merges the two arrays until one of them runs out of elements
• Second loop dumps the remaining elements of array A, if any, into the output array
• Third loop dumps the remaining elements of array B, if any, into the output array

This structure allows you to make the merge loop a lot simpler:

while (aCount != var_a.length() && b.Count != var_b.length()) {
    ... // merge
}
while (aCount != var_a.length()) {
    var_c[cCount++] = var_a[aCount++];
}
while (bCount != var_b.length()) {
    var_c[cCount++] = var_b[bCount++];
}

Note that of the last two loops at most one will be executed. Also note the use of length() method to determine the length of the array. It is more reliable than setting up a_size, b_size, and so on.

Answer 2

this code should follow a simple logic of

1. initialize counters to 0 for all 3 a_counter, b_counter, c_c
2. now while till a_c or b_counter are less than a_size and b_size respectively
   • compare a[a_counter] with b[b_counter] and add the smaller to c at c[c_counter]
   • increment c_counter, and which ever was chosen above
   • repeat
3. once out of loop, one of a or b is over
   • keep adding to c all the remaining elements of a if b is over; or b if a is over I trust you don't need the code, just improvement in logic; so not giving the code.

Answer 3

Instead of iterating over the indices of the merged array, you can iterate over the indices of the individual arrays, to makes sure you never get out of bounds :

int aCount = 0;
int bCount = 0;
int cCount = 0;
while (aCount < var_a.length && bCount < var_b.length) {
    if (var_a[aCount] <= var_b[bCount]) {
        var_c[cCount++] = var_a[aCount++];
    } else {
        var_c[cCount++] = var_b[bCount++];
    }
}
// now add what remains of var_a or var_b
while (aCount < var_a.length)
    var_c[cCount++] = var_a[aCount++];
while (bCount < var_b.length)
    var_c[cCount++] = var_b[bCount++];