Merge two sorted arrays into one

Question

Hi I was asked a following question.

Given two arrays i.e. array1 and array2. Both of them contain numbers in sorted order.

Array1 also contains -1 such as; as many numbers in array2 that many -1's in array1.

Example as follows,

array1 = [-1,-1,-1,-1,56,78,90,1200];
array2 = [1,4,5,1000]

I need to write a program which merge the above arrays in one, which will contain numbers from both the arrays in sorted order, except -1.

This is my code as follows,

 puzzle04([3,6,-1,11,15,-1,23,34,-1,42],[1,12,28]);
 puzzle04([3,6,-1,11,15,-1,23,34,-1,42],[7,19,38]);
 puzzle04([3,6,11,15,32,34,42,-1,-1,-1,-1],[1,10,17,56]);
 puzzle04([-1,-1,-1,-1,3,6,11,15,32,34,42],[1,10,17,56]);
 puzzle04([-1,-1,-1,-1,3,6,11,15,32,34,42],[56,78,90,100]);
 puzzle04([12,34,65,-1,71,85,90,-1,101,120,-1,200],[24,37,94]);
 puzzle04([3,6,-1,11,15,-1,32,34,-1,42,-1],[1,10,17,56]);
 puzzle04([-1,-1,-1,56,78,90,112],[1,4,5]);
 puzzle04([-1,-1,-1,-1,56,78,90,112],[1,4,5,1000]);
 puzzle04([-1,-1,-1,-1,56,78,90,1200],[1,4,5,1000]); 

 function puzzle04(array1,array2){

    var outputArray = [],
        array1Counter = 0, // counter for array1
        array2Counter = 0, // counter for array2
        isArray2NumPlaced = false, // has number from array2 found its position in output array ?       
        areAllArray2NumsFilled = false; // is number pushed in output array

    // iterating through array2 loop    
    for(array2Counter = 0; array2Counter < array2.length; array2Counter++){

        // iterating through array1 loop
        for(; (isArray2NumPlaced === false); array1Counter++){

            // -1 encountered in array1
            if(array1[array1Counter] === -1){ 
                continue;

            // if array1 number is less than array2 number
            // then push array1 number in ouput array   
            }else if(array1[array1Counter] < array2[array2Counter]){

                outputArray.push(array1[array1Counter]);                

            }else{ // array2 number is less then array1 number

                // add array2 number in output array until
                // all array2 numbers are not added in output array.
                if(areAllArray2NumsFilled === false){
                    outputArray.push(array2[array2Counter]);    
                }               


                // is array2 number pushed in output array ?
                isArray2NumPlaced = true;

            }// end of if-else

            // if all the array2 numbers are added in output array
            // but still array1 numbers are left to be added
            if(isArray2NumPlaced === true 
            && array2Counter === (array2.length - 1) 
            && array1Counter <= (array1.length - 1)){

                outputArray.push(array1[array1Counter]);    

                // set the below flag to false so that,
                // array1 loop can iterate
                isArray2NumPlaced = false;

                // all the numbers of array2 are entered in output array
                areAllArray2NumsFilled = true;

            }// end of if

        }// array1 for-loops ends



        array1Counter--;
        isArray2NumPlaced = false;

    }// array2 for-loops ends


    console.log("final ",outputArray);  
}

The output of the above code is as follows,

final  [ 1, 3, 6, 11, 12, 15, 23, 28, 34, 42 ]
final  [ 3, 6, 7, 11, 15, 19, 23, 34, 38, 42 ]
final  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]
final  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]
final  [ 3, 6, 11, 15, 32, 34, 42, 56, 78, 90, 100 ]
final  [ 12, 24, 34, 37, 65, 71, 85, 90, 94, 101, 120, 200 ]
final  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]
final  [ 1, 4, 5, 56, 78, 90, 112 ]
final  [ 1, 4, 5, 56, 78, 90, 112, 1000 ]
final  [ 1, 4, 5, 56, 78, 90, 1000, 1200 ]

When I showed my code to reviewer, he said I used too much boolean variables and the code can be lot more simpler.

I tried my best to improvise, but didn't got any clue.

Can you please suggest me any better way to solve above problem

Note: can't use any ready-made sorting methods or pre written api to solve above excercise.

Answer 1

All you have to do is step through both arrays, take the smaller of the two values, and add it to the output list. Once you have added all of one array, the remainder of the other array is all larger, and can be added in one go.

function merge(x, y) {
    var i = 0;
    var j = 0;
    var result = [];

    while (i < x.length && j < y.length) {
        // Skip negative numbers
        if (x[i] === -1) {
            x += 1;
            continue;
        }
        if (y[j] === -1) {
            y += 1;
            continue;
        }

        // Take the smaller of the two values, and add it to the output.
        // Note: the index (i or j) is only incremented when we use the corresponding value
        if (x[i] <= y[j]) {
            result.push(x[i]);
            i += 1;
        } else {
            result.push(y[j]);
            j += 1;
        }
    }

    // At this point, we have reached the end of one of the two arrays. The remainder of
    // the other array is all larger than what is currently in the output array

    while (i < x.length) {
        result.push(x[i]);
        i += 1;
    }

    while (j < y.length) {
        result.push(y[j]);
        j += 1;
    }

    return result;
}