# Merged integer sorted arrays

One of classic problem using binary search approach.

## Problem

Given two sorted integer arrays A and B, merge B into A as one sorted array.

## Solution

The key to solve this problem is moving element of A and B backwards. If B has some elements left after A is done, also need to handle that case. The takeaway message from this problem is that the loop condition.

### Solution 1

In this case We have two arrays A and B, but array A have m elements to merge, and m+n placeholders for all elements.

```public class Solution {
public void merge(int A[], int m, int B[], int n) {

while(m > 0 && n > 0){
if(A[m-1] > B[n-1]){
A[m+n-1] = A[m-1];
m--;
}else{
A[m+n-1] = B[n-1];
n--;
}
}

while(n > 0){
A[m+n-1] = B[n-1];
n--;
}
}
}
```

Memory O(0) (uses only arrays what we have), Steps: O(m+n) - linear

### Solution 2

```public void merge(int A[], int m, int B[], int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;

while (k >= 0) {
if (j < 0 || (i >= 0 && A[i] > B[j]))
A[k--] = A[i--];
else
A[k--] = B[j--];
}
}
```

Memory O(3); Steps: O(m+n)