# If given two sorted arrays where first containing -1, merge into one sorted array

If given two arrays

arrayOne = [3,6,-1,11,15,-1,32,34,-1,42,-1]
arrayTwo = [1,10,17,56]


Both the array's are sorted but array1 consists -1 in between the sorted numbers.

Now to problem is to merge numbers present in array2 into array1 so that array1 should be sorted and should not contain -1.

i.e.

arrayOne =  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]


For the above problem I created one algorithm it is as follows,

step1 : iterate through array2, compare with number present in array1, if number in array2 is less and number in array1, than swap the numbers.

step2 : continue iterating through array1 till -1 occures, now swap.

step3 : got to step1.

so the working of above algorithm is as follows,

step1,

array1 = [3,6,-1,11,15,-1,32,34,-1,42,-1]
array2 = [1,10,17,56]


step2(swaped):

array1 = [1,6,-1,11,15,-1,32,34,-1,42,-1]
array2 = [3,10,17,56]


step3(swaped)

array1 = [1,3,-1,11,15,-1,32,34,-1,42,-1]
array2 = [6,10,17,56]


step4(swaped)

array1 = [1,3,6,11,15,-1,32,34,-1,42,-1]
array2 = [-1,10,17,56]


step5(swaped)

array1 = [1,3,6,10,15,-1,32,34,-1,42,-1]
array2 = [-1,11,17,56]


Continue as above,

The code for above problem is

puzzle02([3,6,-1,11,15,-1,32,34,-1,42,-1],[1,10,17,56]);

function puzzle02(arrayOne,arrayTwo){
var array1Counter = 0,
array2Counter = 0,
hasMinusOneOccurred = false;

console.log(" array-1 ",arrayOne);
console.log(" array-2 ",arrayTwo);

while(array2Counter < arrayTwo.length){ // iterate through array2

do{
if(arrayOne[array1Counter] === -1){ // if -1 occurred in array1
hasMinusOneOccurred = true;

// swaping numbers at current position of array1
// with current position of array2
swap(arrayOne,arrayTwo,array1Counter,array2Counter);

// recheck if the current value is greater than other values
// of array1
if(recheckAndSort(arrayOne,array1Counter) === true){
array1Counter = -1;// recheck array1 from start
}else{
// recheck the current array1 counter, for doing so go 1 count back
// so that even if the counter is incremented it points to current
// number itself
array1Counter--;
}

}else if(arrayOne[array1Counter] > arrayTwo[array2Counter]){
swap(arrayOne,arrayTwo,array1Counter,array2Counter);
}else{
array1Counter++;
continue;
}

array1Counter++;
}while(hasMinusOneOccurred === false); // end of do-while

array2Counter++;
hasMinusOneOccurred = false;

}//end of while

console.log(" Sorted array ",arrayOne);

function swap(arr1,arr2,arr1Index,arr2Index){
var temp = arr2[arr2Index];
arr2[arr2Index] = arr1[arr1Index];
arr1[arr1Index] = temp;
}// end of swap

// this method is call if -1 occures in array1
function recheckAndSort(arrayOne,array1Counter){
var isGreaterVal = true,
prevCounter = 0,
nextCounter = 0,
temp = 0,
recheckFromStart = false;

if(array1Counter === 0){ // if -1 occurred at first position of array1.

// flag to check if -1 occurrec at first position
// if yes, iterate array1 from start
recheckFromStart = true;

// iterate forward to check wether any numbers are less than current position,
// if yes than move forward
for(var j = 0; isGreaterVal; j++){
nextCounter = j + 1;

if(arrayOne[nextCounter] === -1){
// swaping numbers of array1 between next to current
swap(arrayOne,arrayOne,nextCounter,j);
isGreaterVal = true;

}else if(arrayOne[nextCounter] < arrayOne[j]){
// swaping numbers of array1 between next to current
swap(arrayOne,arrayOne,nextCounter,j);
isGreaterVal = true;

}else{
isGreaterVal = false;
}

}//end of for

}else{// if -1 occurred in the middle position of array1 and is been swaped then
// iterate backwards to check if any number less then current position exists,
// if yes than shift backwards.
for(var i = array1Counter; isGreaterVal; i--){
prevCounter = i - 1;

if(arrayOne[prevCounter] > arrayOne[i]){

// swaping numbers of array1 between previous to current
swap(arrayOne,arrayOne,prevCounter,i);
isGreaterVal = true;
}else{
isGreaterVal = false;
}

}// end of for
}

return recheckFromStart;
}// end of recheckAndSort
} // end of puzzle02


The output of above code is

array-1  [ 3, 6, -1, 11, 15, -1, 32, 34, -1, 42, -1 ]
array-2  [ 1, 10, 17, 56 ]
Sorted array  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]


Can my logic as explained above can be improved further or is there a better solution of the above problem