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

# 4.Merge Two Sorted Array

Given two sorted integer arrays `nums1` and `nums2`, merge `nums2` into `nums1` as one sorted array.

The number of elements initialized in `nums1` and `nums2` are `m` and `n` respectively. You may assume that `nums1` has a size equal to `m + n` such that it has enough space to hold additional elements from `nums2`.

**Example 1:**

```
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
```

**Example 2:**

```
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
```

## Solution I

```cpp
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> v;
        int i=0,j=0;
        while(i<m && j<n){
            if(nums1[i] <= nums2[j]){
                v.push_back(nums1[i]);
                i++;
            }
            else{
                v.push_back(nums2[j]);
                j++;
            }
            
        }
        
        while(i<m){
            v.push_back(nums1[i]);
            i++;
        }
        
        while(j<n){
          v.push_back(nums2[j]);
          j++;
        }
        
        
        for(int i=0;i<v.size();i++){
            nums1[i] = v[i];
        }
        
    }
};
```

**This algorithm uses a Time Complexity :O(n) but uses an Extra Space Complexity:O(n)**

## Solution II

```cpp
class Solution
{
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
    {
        
        int s = (m + n) - 1;
        m = m - 1;
        n = n - 1;
       
        while (n >= 0)
        {
            if (m>=0 && nums1[m] >= nums2[n])
            {
                nums1[s] = nums1[m];
                m--;
            }
            else
            {
                nums1[s] = nums2[n];
                n--;
            }
            s--;
        }
    }
};
```

**This algorithm uses a Time Complexity :O(n), Space Complexity: O(1)**