     ## 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 static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = a.length - 1, j = b.length - 1, k = answer.length;

while (k > 0)
(j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
}
```

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

### Solution 3

```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(1); Steps: O(m+n)