# Merge sorted array

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

You may assume that A has enough space (size that is greater or equal to _m_ + _n_) to hold additional elements from B. The number of elements initialized in A and B are _m_ and _n_ respectively.Have you met this question in a real interview?  Yes

#### Example

A = `[1, 2, 3, empty, empty]`, B = `[4, 5]`

After merge, A will be filled as `[1, 2, 3, 4, 5]`

由于合并后A数组的大小必定是m+n，所以从最后面开始往前赋值，先比较A和B中最后一个元素的大小，把较大的那个插入到m+n-1的位置上，再依次向前推。如果A中所有的元素都比B小，那么前m个还是A原来的内容，没有改变。如果A中的数组比B大的，当A循环完了，B中还有元素没加入A，直接用个循环把B中所有的元素覆盖到A剩下的位置。

```java
public class Solution {
    /*
     * @param A: sorted integer array A which has m elements, but size of A is m+n
     * @param m: An integer
     * @param B: sorted integer array B which has n elements
     * @param n: An integer
     * @return: nothing
     */
    public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        // write your code here
        int index = m + n - 1;
        m--;
        n--;
        while(m >= 0 && n >= 0 ){
            A[index--] = A[m] > B[n] ? A[m--] : B[n--];
        }
        
        while(m >= 0){
            A[index--] = A[m--];
        }
        
        while(n >= 0){
            A[index--] = B[n--];
        }
    }
}
```

