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

Question

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 ]

Please review my code, and give your valuable feedback.

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

Please suggest me.

Answer 1

I have a couple of thoughts I wanted to share after taking some time to work through this problem.

1. Your code has a potential bug: If I add any elements to "array-2", the while loop becomes an infinite loop.
2. If you want to extend some functionality to your code, add a 3rd array as an argument. This array will contain all the values you want to filter out. Then write up a subroutine to filter out those values.
3. Another way to extend the code would be to add a "checking" function that can ensure that all the arrays entered are in numerical order before running through the merge sort algorithm. I didn't add this to mine, but it could add some a level of robustness that doesn't exist now.

I took a shot at writing up a version of this code, you can check it out if you want to compare notes.