# Merge two arrays and sort the final one

In an interview I was asked the following question. I am given two arrays, both of them are sorted.

BUT

Array 1 will have few -1's and Array 2 will have total numbers as the total number of -1's in Array 1.

So in the below example array1 has three -1's hence array2 has 3 numbers.

let say

``````var arrayOne = [3,6,-1,11,15,-1,23,34,-1,42];
var arrayTwo = [1,9,28];
``````

Both of the arrays will be sorted.

Now I have to write a program that will merge arrayTwo in arrayOne by replacing -1's, and arrayOne should be in sorted order.

So the output will be

``````arrayOne = [ 1,3, 6, 9, 11, 15, 23, 28 ,34, 42 ]
``````

Sorting should be done without use of any sort API.

I have written a following code

``````function puzzle01() {
var arrayOne = [3, 6, -1, 11, 15, -1, 23, 34, -1, 42];
var arrayTwo = [1, 9, 28];
var array1Counter = 0,
isMerged = false;

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

for (var array2Counter = 0; array2Counter < arrayTwo.length; array2Counter++) {
isMerged = false;
while (isMerged === false && array1Counter < arrayOne.length) {

if (arrayOne[array1Counter] === -1) {
arrayOne[array1Counter] = arrayTwo[array2Counter];
isMerged = true;
}

array1Counter++;
}
} //for

console.log(" array-1 + array-2 ", arrayOne);
bubbleSort(arrayOne);
console.log(" Sorted array ", arrayOne);
} //puzzle01

puzzle01();

// implementation of bubble sort for sorting the
// merged array
function bubbleSort(arrayOne) {
var nextPointer = 0,
temp = 0,
hasSwapped = false;

do {
hasSwapped = false;
for (var x = 0; x < arrayOne.length; x++) {
nextPointer = x + 1;
if (nextPointer < arrayOne.length && arrayOne[x] > arrayOne[nextPointer]) {
temp = arrayOne[x];
arrayOne[x] = arrayOne[nextPointer];
arrayOne[nextPointer] = temp;
hasSwapped = true;
}
} //for
} while (hasSwapped === true);
} // bubbleSort``````

The output of the above code is

`````` array-1  [ 3, 6, -1, 11, 15, -1, 23, 34, -1, 42 ]
array-2  [ 1, 9, 28 ]
array-1 + array-2  [ 3, 6, 1, 11, 15, 9, 23, 34, 28, 42 ]
Sorted array  [ 1, 3, 6, 9, 11, 15, 23, 28, 34, 42 ]
``````

From the above code you can see, I have first merged the two arrays and than sorted the final one.

Just wanted to know, Is there a better solution.

Is there any flaw in my solution.

Let us take an example

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

Step1: I will iterate through arrayTwo. Take the next element (i.e. '1') and compare with next element of arrayOne (i.e. '3') and compare.

step 2a : If element of array1 is greater than element of array2 than swap array elements. Now go to next element of array1.

OR

step 2b : If element of array1 is equal to -1 than swap array elements. Now go to next element of array2.

step 3: Go to step 1.

So

in the above example

first iteration, array1 = [1,6,-1,11,...] array2 = [3,10,17,56]

second iteration, array1 = [1,3,-1,11,..] array2 = [6,10,17,56]

third iteration, array1 = [1,3,6,11..] array2 = [-1,10,17,56]

fourth iteration array1 = [1,3,6,10,..] array2 = [-1,11,17,56]

and so on.

at the end I will get the output

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

``````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
``````

After calling the above function

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

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 ]
``````

Thanks.

You can try following approach:

### Logic

• Create a new array that will be returned.
• Check for first element in `arrayTwo` and keep it in a variable say `val`.
• Loop over `arrayOne` and check if current value is greater than `val`, push it in array and decrement value of `i` by 1 to check next value as well with current element.
• Now check for current element. If it is less than `0`, ignore it, else push value to array.
• Return this array.

``````function mergeAndSort(a1, a2) {
var matchCount = 0;
var ret = [];

for (var i = 0; i < a1.length; i++) {
var val = a2[matchCount];
if (a1[i] > val) {
ret.push(val)
matchCount++
i--;
continue;
}
if (a1[i] > 0) {
ret.push(a1[i]);
}
}
console.log(ret.join())
return ret;
}

var arrayOne = [3, 6, -1, 11, 15, -1, 23, 34, -1, 42]
var arrayTwo = [7, 19, 38];
var arrayThree = [1, 9, 28];
var arrayFour = [1,2,5]

mergeAndSort(arrayOne, arrayTwo)
mergeAndSort(arrayOne, arrayThree)
mergeAndSort(arrayOne, arrayFour)``````
``````.as-console-wrapper {
max-height: 100% !important;
top: 0;
}``````

Note: Not putting check for number of elements in `arrayTwo` as its clearly mentioned in question that it will be same.

There is a clean O(N) in-place solution.

First "pack" `arrayOne` by moving all `-1` (`--` below) to the front. This takes a single backward pass.

Then perform a merge by iteratively moving the smallest element among `arrayTwo` and the tail of `arrayOne` and overwriting the next `--`. The gap will narrow down but there will always remain room for the elements of `arrayTwo`.

`````` 3,  6, --, 11, 15, --, 23, 34, --, 42
1,  9, 28
``````

Packing:

`````` 3,  6, --, 11, 15, --, 23, 34, --, 42

3,  6, --, 11, 15, --, 23, --, 34, 42

3,  6, --, 11, 15, --, --, 23, 34, 42

3,  6, --, 11, --, --, 15, 23, 34, 42

3,  6, --, --, --, 11, 15, 23, 34, 42

3, --, --, --,  6, 11, 15, 23, 34, 42

--, --, --, 3,  6, 11, 15, 23, 34, 42
``````

Merging:

``````  --, --, --,  3,  6, 11, 15, 23, 34, 42
1,  9, 28

1, --, --,  3,  6, 11, 15, 23, 34, 42
--,  9, 28

1,  3, --, --,  6, 11, 15, 23, 34, 42
--,  9, 28

1,  3,  6, --, --, 11, 15, 23, 34, 42
--,  9, 28

1,  3,  6,  9, --, 11, 15, 23, 34, 42
--, --, 28

1,  3,  6,  9, 11, --, 15, 23, 34, 42
--, --, 28

1,  3,  6,  9, 11, 15, --, 23, 34, 42
--, --, 28

1,  3,  6,  9, 11, 15, 23, --, 34, 42
--, --, 28

1,  3,  6,  9, 11, 15, 23, 28, 34, 42
--, --, --
``````

You should do something like `insertion sort`. As both the arrays are sorted (except -1s), the smallest number in `array2` will be placed somewhere between first element and the first -1, 2nd element of `array2` will be placed somewhere anywhere after the 1st -1 in `array1` and before or at the 2nd -1 in `array1` and so on.

So you have to insert a particular element of `array2` in only a segment of `array1` and not the whole array. Also each element of `array2` have to consider different segment or subarray of `array1`. So, effective time complexity of this logic will be `O(n+m)` where `n` is the length of `array1` and `m` is the length of `array2`.

Couldn't it be something like

compare each item of arrayTwo with each item of arrayOne If it comes to bigger that that of arrayOne, insert the item and while iterating arrayOne delete all the -1 .

That's actually an interesting question. There are many sorting algorithms, and the most efficient ones always starts from one "unchangeable" array, so without changing the values inside that. Yet here your goal is to change the value when it encounters -1, so that the value is taken from the second array.

So, you need a sorting algorithm that doesn't divide the array in pieces because if the last element of your second array is 1 (the lowest), it has to be moved to the start. If you're using a sorting algorithm that breaks the array in pieces (the divide-and-conquer tactic like quick sort) or that uses recursion, it can be problematic because it cannot be moved to the start of your main array. Unless you are aware of the main array.

What you need is an algorithm that performs a step-by-step algorithm.

The algorithm that I've used is a bubble sort, which checks each element step by step. It's then easier to replace the value if it's -1 and move its position correctly to the array. However, it is not so efficient. Maybe I will edit my post to see if I can improve that.

``````function mergeAndSort(arr1, arrMergeIn) {
// merge + sort using arr1 as large one
var mergeIndex = 0;

for (var i = 0; i < arr1.length; ++i) {
if (arr1[i] === -1) arr1[i] = arrMergeIn[mergeIndex++];
var j = i;
while (j > 0 && arr1[j - 1] > arr1[j]) {
var tmp = arr1[j - 1];
arr1[j - 1] = arr1[j];
arr1[j] = tmp;
j--
}
}
return arr1;
}

// one liner console output
function showArray(arr) {
console.log(arr.join(','));
}

showArray(mergeAndSort([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [7, 19, 38]));

showArray(mergeAndSort([3, 36, -1, 1, 10, -1, 9, 34, -1, 42], [17, 9, 38]));

showArray(mergeAndSort([3, 36, -1, 1, 10, -1, 9, 34, -1, 42], [17, 9, 1]));

showArray(mergeAndSort([-1, 36, -1, 1, 10, -1, 9, 34, -1, 42], [17, 9, 100, 1]));

showArray(mergeAndSort([-1, -1, 1, 100, -1, 9, 34, -1], [17, 9, 9, 1]));``````

Or, you can use another strategy: replace the "-1" elements with the elements from that another array and perform an efficient algorithm on that. Although in worst-case scenario's, the "-1"s are at the end of the array, which means that there is an ~N operation + additional average complexity of a sorting algorithm (the efficient ones are of ~N*log(N))

You could iterate `arrayOne` in a single loop and then `arrayTwo`.

The idea is to separate the target index from the actual index. The first loop ignores `-1` and and keep the target index.

If an actual value is greater then the first value of `arrayTwo`, both values swapped and in arrayTwo takes a sorting place by iterating and swapping with grater values.

Then the actual item is assigned to the target index.

Both indices gets incremented.

At the end all items of `arrayTwo` are added to `arrayOne`.

``````function order(arrayOne, arrayTwo) {
var i = 0, j, l = 0;
while (i < arrayOne.length) {
if (arrayOne[i] === -1) {
i++;
continue;
}
if (arrayTwo[0] < arrayOne[i]) {
[arrayOne[i], arrayTwo[0]] = [arrayTwo[0], arrayOne[i]];
j = 0;
while (arrayTwo[j] > arrayTwo[j + 1]) {
[arrayTwo[j], arrayTwo[j + 1]] = [arrayTwo[j + 1], arrayTwo[j]];
j++;
}
}
arrayOne[l++] = arrayOne[i++];
}
j = 0;
while (l < arrayOne.length) {
arrayOne[l++] = arrayTwo[j++];
}
return arrayOne;
}

console.log(order([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [7, 19, 38]));
console.log(order([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [1, 9, 28]));
console.log(order([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [1, 2, 5]));
console.log(order([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [43, 44, 45]));``````
``.as-console-wrapper { max-height: 100% !important; top: 0; }``

Here is a simple and compact implementation of the merge sort algorithm. There will only be the same amount of operations as there are elements.

I achieve this by creating an array with the same number of elements as both arrays combined, then iterating that array.

Upon each iteration:

• If both arrays have elements (and the smallest element is not -1) it will move the smallest element into the result.
• If only one of the arrays still has elements (and the next element is not -1), it will move the first element from that array into the result.

Finally assign the result to the first array as per your spec

``````const mergeSort = (a, b) => Object.assign(a,
new Int32Array(a.length + b.length).reduce(m => {
const el = [
[a, b][+!(a[0] <= b[0])],
[a, b][+!a.length]][+!(a.length && b.length)
].shift()
if(el !== -1) m.push(el)
return m
}, [])
)

const arr1 = [1,3,5,7,9]
const arr2 = [0,2,4]

mergeSort(arr1, arr2)

console.log(arr1) // [0,1,2,3,4,5,7,9]``````

Let me re-phrase three most important aspects of the task:

• Both arrays are sorted and include positive integers (except -1 place-holders in Array1)
• The -1 is meaningless placeholder (its position in Array1 is random)
• Array1 length equals output array length

Pseudo logic:

• parse both array1 and array2 from the first position to end of array
• ignore -1 values in array1
• if array1[current position] <= array2[current position] then write array1[current position] into merged array and move to next position in array1; otherwise apply same for array2

Code example:

``````            public static void AMerge()
{
int[] array1 = new int[] { 3, 6, -1, 11, 15, -1, 23, 34, -1, 42 };
int[] array2 = new int[] { 1, 9, 28 };
int[] arrayMerged = new int[array1.Length];

int array1Index = 0;
int array2Index = 0;

for (int arrayMergedIndex = 0; arrayMergedIndex < array1.Length; arrayMergedIndex++)
{
while (array1[array1Index] == -1) array1Index++; //ignore -1 placeholders
if ((array1Index < array1.Length && array2Index >= array2.Length)
|| array1[array1Index] <= array2[array2Index])  //choose which array will provide current merged value
{
arrayMerged[arrayMergedIndex] = array1[array1Index];
array1Index++;
}
else
{
arrayMerged[arrayMergedIndex] = array2[array2Index];
array2Index++;
}
}

char[] charsToTrim = { ',', ' '};
string arrayMergedString = "{";
foreach (int f in arrayMerged) arrayMergedString += f.ToString() + " ";
arrayMergedString = arrayMergedString.TrimEnd(charsToTrim) + "}";
Console.WriteLine(arrayMergedString);
}
}
``````

Note:

• Optimizing for speed => creating new arrayMerged; optimization for space would require moving array1 elements in the else branch

You should use merge function from Merge sort, and modify it so that it doesn't create a new array, but instead uses array1, and perform translation, after insertion of an element from array2, that will shift elements to the right until the next -1, and thus overwrite the -1.

``````function merger(a1, a2) {
var i = 0;
var j = 0;

while (i < a1.length && j < a2.length) {
if (a1[i] > a2[j]) {
// Swap values
var temp = a2[j];
a2[j] = a1[i];
a1[i] = temp;
i++;
} else if (a1[i] !== -1 && a1[i] <= a2[j]) {
i++;
} else {
var temp = a2[j];
a2[j] = a1[i];
a1[i] = temp;
i++;
j++;
}
}

return a1;
}

var arrayOne = [3, 5, -1, 11, 15, -1, 23, 34, -1, 42];
var arrayTwo = [6, 19, 38];

console.log(merger(arrayOne, arrayTwo))``````

With certain pre-conditions (no other numbers with <0, a1 should be smaller than a2 etc - which could all be handled) this should solve the problem in JS.

Since they are both sorted, the order of `arrayTwo`'s items should match the order of `-1`s in `arrayOne`. Then the job becomes simple and can be implemented as follows;

``````function replaceMissing(a,b){
var i = 0;
return a.map(n => n < 0 ? b[i++] : n);
}
var arrayOne = [3,6,-1,11,15,-1,23,34,-1,42],
arrayTwo = [7,19,38];
result = replaceMissing(arrayOne,arrayTwo);
console.log(result);``````

Edit: I believe the upper solution does make more sense in the general logic of the question. If the position of -1s does not mean anything then what use do they have? Let's just delete the -1's and do a simple insertion of `arrayTwo` items at proper indices in `arrayOne`. This can very simply be done as follows.

``````function replaceMissing(a,b){
var j = b.length-1;
return b.concat(a.reduceRight((r,m,i) => (m < 0 ? r.splice(i,1)
: m < b[j] && r.splice(i+1,0,b.splice(j--,1)[0]),
r), a.slice()));
}
var arrayOne = [3,6,-1,11,15,-1,23,34,-1,42],
arrayTwo = [1,25,38];
result = replaceMissing(arrayOne,arrayTwo);
console.log(result);``````