# Merge Sorted Array II

## Question

Merge two given sorted integer array A and B into a new sorted integer array.

Example
A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]

Challenge
How can you optimize your algorithm
if one array is very large and the other is very small?


## 題解

### Python

class Solution:
#@param A and B: sorted integer array A and B.
#@return: A new sorted integer array
def mergeSortedArray(self, A, B):
if A is None or len(A) == 0:
return B
if B is None or len(B) == 0:
return A

C = []
aLen, bLen = len(A), len(B)
i, j = 0, 0
while i < aLen and j < bLen:
if A[i] < B[j]:
C.append(A[i])
i += 1
else:
C.append(B[j])
j += 1

# A has elements left
while i < aLen:
C.append(A[i])
i += 1

# B has elements left
while j < bLen:
C.append(B[j])
j += 1

return C


### C++

class Solution {
public:
/**
* @param A and B: sorted integer array A and B.
* @return: A new sorted integer array
*/
vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
if (A.empty()) return B;
if (B.empty()) return A;

int aLen = A.size(), bLen = B.size();
vector<int> C;
int i = 0, j = 0;
while (i < aLen && j < bLen) {
if (A[i] < B[j]) {
C.push_back(A[i]);
++i;
} else {
C.push_back(B[j]);
++j;
}
}

// A has elements left
while (i < aLen) {
C.push_back(A[i]);
++i;
}

// B has elements left
while (j < bLen) {
C.push_back(B[j]);
++j;
}

return C;
}
};


### Java

class Solution {
/**
* @param A and B: sorted integer array A and B.
* @return: A new sorted integer array
*/
public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
if (A == null || A.isEmpty()) return B;
if (B == null || B.isEmpty()) return A;

ArrayList<Integer> C = new ArrayList<Integer>();
int aLen = A.size(), bLen = B.size();
int i = 0, j = 0;
while (i < aLen && j < bLen) {
if (A.get(i) < B.get(j)) {
i++;
} else {
j++;
}
}

// A has elements left
while (i < aLen) {
i++;
}

// B has elements left
while (j < bLen) {
j++;
}

return C;
}
}