> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/array/merge-sorted-arrays.md).

# Merge Sorted Arrays

{% hint style="info" %}
Array, Two Pointers
{% endhint %}

Given two integer arrays `nums1` and `nums2`, sorted in non-decreasing order.

### Solutions

#### Approach - **Brute Force Technique**

This method also returns a new array that is a sorted merge of the input arrays. However, it does this by first concatenating the two input arrays into one larger array, and then sorting this larger array.

**Steps**

1. **Initialize mergedArray**: A new integer array `mergedArray` is created with a length equal to the sum of the lengths of `nums1` and `nums2`. This array will hold the merged result of `nums1` and `nums2`.
2. **Copy nums1 to mergedArray**: The elements of `nums1` are copied into `mergedArray`, starting at the beginning of `mergedArray`.
3. **Copy nums2 to mergedArray**: The elements of `nums2` are copied into `mergedArray`, starting at the position immediately after the last element of `nums1` in `mergedArray`.
4. **Sort mergedArray**: The `Array.Sort` method is called to sort `mergedArray` in non-decreasing order. This is necessary because the elements of `nums1` and `nums2` were simply concatenated, not merged in a sorted manner.
5. **Return mergedArray**: Finally, `mergedArray` is returned as the result of the method. This array contains all the elements of `nums1` and `nums2`, sorted in non-decreasing order.

<pre class="language-csharp"><code class="lang-csharp">public class Solution
{
    public int[] MergeArrays(int[] nums1, int[] nums2)
    {
        int[] mergedArray = new int[nums1.Length + nums2.Length];
        nums1.CopyTo(mergedArray, 0);
        nums2.CopyTo(mergedArray, nums1.Length);
        Array.Sort(mergedArray);
        return mergedArray;
<strong>    }
</strong>
}
</code></pre>

> Complexity

* **Time complexity:** `O((N+M) log (N+M))`
* **Space complexity:** `O(N+M)`

The time complexity of the `MergeArrays` method can be more accurately described as **O((N+M) log (N+M))**, where **N** is the size of the first array and **M** is the size of the second array. This is because the `Array.Sort` function is called on the merged array, which has a size of `N+M`, and the time complexity of sorting is `O(n log n)`, where n is the size of the array being sorted. So in this case, n is N+M. Therefore, the time complexity is `O((N+M) log (N+M))`.

The space complexity of the algorithm is **O(N + M)**. This is because a new array of size `N + M` is created to store the result. The space used by this array grows linearly with the size of the input arrays, hence the linear space complexity.&#x20;

#### **Approach - Two Pointers**

This method works by maintaining two pointers, one for each input array. The pointers are initially set to the start of their respective arrays. The method then compares the elements at the current pointer positions in both arrays, and the smaller of the two elements is added to the merged array. The pointer for the array from which an element was taken is then incremented. If one of the arrays is exhausted before the other, the remaining elements from the non-exhausted array are copied into the merged array. The method finally returns the merged array. This technique ensures that the merged array is also sorted in non-decreasing order.

**Steps**

1. **Initialization**: The function `MergeArrays` is defined with two parameters, `nums1` and `nums2`, which are the input arrays. It initializes a new array `result` with a length equal to the sum of the lengths of `nums1` and `nums2`. Three pointers `i`, `j`, and `k` are also initialized to 0. `i` and `j` will be used to traverse `nums1` and `nums2` respectively, and `k` will be used to insert elements into `result`.
2. **Traverse Both Arrays**: The function enters a loop that continues as long as `i` is less than the length of `nums1` and `j` is less than the length of `nums2`. This ensures that we only consider elements that are within the bounds of both arrays.
3. **Compare and Insert Elements**: Inside the loop, the function checks if the current element of `nums1` (pointed to by `i`) is less than the current element of `nums2` (pointed to by `j`). If it is, the element from `nums1` is inserted into `result` at the position pointed to by `k`, and `i` and `k` are incremented. If not, the element from `nums2` is inserted into `result`, and `j` and `k` are incremented. This ensures that the smaller of the two current elements is always inserted into `result`.
4. **Store Remaining Elements**: After the loop, there may be remaining elements in `nums1` or `nums2` (but not both). Two additional loops are used to insert any such remaining elements into `result`. The first loop inserts remaining elements from `nums1`, and the second loop inserts remaining elements from `nums2`.
5. **Return Result**: Finally, the function returns `result`, which is a sorted array containing all elements from `nums1` and `nums2`.

```csharp
public int[] MergeArrays(int[] nums1, int[] nums2)
{
    int[] result = new int[nums1.Length + nums2.Length];
    int i = 0, j = 0, k = 0;

    // Traverse both arrays
    while (i < nums1.Length && j < nums2.Length)
    {
        // Check if current element of first array is smaller than current element of second array
        if (nums1[i] < nums2[j])
            result[k++] = nums1[i++];
        else
            result[k++] = nums2[j++];
    }

    // Store remaining elements of first array
    while (i < nums1.Length)
        result[k++] = nums1[i++];

    // Store remaining elements of second array
    while (j < nums2.Length)
        result[k++] = nums2[j++];

    return result;
}

```

> Complexity

* **Time complexity:** `O(N+M)`
* **Space complexity:** `O(N+M)`

The time complexity of the merge algorithm is **O(n + m)**, where **n** and **m** are the lengths of the two input arrays, `nums1` and `nums2`. This is because in the worst case, the algorithm needs to iterate over all elements in both arrays once.

The space complexity of the algorithm is **O(n + m)**. This is because a new array of size `n + m` is created to store the result. The space used by this array grows linearly with the size of the input arrays, hence the linear space complexity. The rest of the variables used in the algorithm (`i`, `j`, and `k`) use a constant amount of space.