Search code examples
c++arraysalgorithmmergearray-merge

Having trouble with merge function algorithm in C++


I have been trying to figure out what could possibly be going wrong with the calling of these two functions for a while now and can't seem to identify it. When I call the merge function before the show function, it works fine and merges the two arrays and then shows them Otherwise, if I call the merge function after any other function (such as the show(a,els) and show(b,els)), the merge function does not work and outputs all zeroes in the merged array. Any ideas would be very helpful.

int main(){
    const unsigned els = 5;
    unsigned a[els] = {1,2,3,4,5};
    unsigned b[els] = {1,2,3,4,4};
    unsigned combo[(els*2)];

    show( a, els);
    show( b, els);

    merge( combo, a, els, b, els);
    show( combo, els*2);

    return 0;
}

void show( const unsigned a[], unsigned elements ){
    cout << "[" << elements << "]: ";
    for ( unsigned i = 0; i < elements; i++)
    {
        cout << a[i]; //Outputting contents of array
        if(i != elements-1)
            cout << ","; 
    }
    cout << endl;
}


void merge( unsigned combo[], const unsigned a[], unsigned aElements, const
unsigned b[], unsigned bElements ){

    string notsort(" Array is not sorted");
    if((!sorted(a, aElements)) || (!sorted(b, bElements)))
        die(notsort);

    unsigned i,j,k = 0;
    while(i < aElements && j < bElements){
        if(a[i] <= b[j]){
            combo[k]= a[i];
            i++;
        } else {
            combo[k] = b[j];
            j++;
        }
        k++;
    }
    if(i < aElements){
        for(int x = i; x < aElements; x++){
            combo[k] = a[x];
            k++;
        }
    }else{
        for(int x = j; x < bElements; x++){
            combo[k] = b[x];
            k++;
        }
    }
}

Output with merge function after show of a and b:

[5]: 1,2,3,4,5
[5]: 1,2,3,4,4
[10]: 0,0,0,0,0,0,0,0,0,0

Output with merge function before show of a and b:

[10]:1,1,2,2,3,3,4,4,4,5
[5]: 1,2,3,4,5
[5]: 1,2,3,4,4

Solution

  • You have undefined behavior in the merge function, because you don't initialize the i or j variables. That means their value is indeterminate (and in reality will be seemingly random).

    When declaring variable, you need to initialize every variable separately, you can't do like you do now and hope all variables will be initialized.

    So change from

    unsigned i,j,k = 0;
    

    to

    unsigned i = 0, j = 0, k = 0;