> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/array/merge-sorted-array-ii.md).

# Merge Sorted Array Ii

## Merge Sorted Array Ii

## 题目地址

<https://www.lintcode.com/problem/merge-sorted-array/description>

## 题目描述

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

## 代码

```java
public class Solution {
    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)) {
        C.add(A.get(i));
        i++;
      } else {
        C.add(B.get(j));
        j++;
      }
    }

    while (i < aLen) {
      C.add(A.get(i));
      i++;
    }

    while (j < bLen) {
      C.add(B.get(j));
      j++;
    }

    return C;
  }
}
```