Sorting: Merge 2 sorted arrays

Problem Statement:

You are given 2 arrays, you need to merge 2 sorted arrays

Example:

Input: a = [1, 2, 3, 4, 4, 5] b = [6, 6, 7, 8, 9]

Output: result = [1, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9]

Solution : Naive Approach

Combine the elements of both the arrays into resultant array.

Sort the array

Time Complexity: O((n1 + n2) log(n1 + n2))
Space Complexity: O(1)

Solution : Merge sort Approach

Start traversing a[] and b[] array at the same time.

Choose smaller of current elements from a[] and b[] and copy this smaller element into the resultant array

If there are remaining elements from both the arrays, copy into resultant array

Time Complexity: O(n1 + n2)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>

using namespace std;


void solution_1 (vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) 
{
    int n1 = arr1.size();
    int n2 = arr2.size();
    int i = 0, j = 0, k = 0;

    while (i < n1) 
    {
        arr3[k++] = arr1[i++];
    }

    while (j < n2) 
    {
        arr3[k++] = arr2[j++];
    }

    sort(arr3.begin(), arr3.end());
}

void solution_2 (vector<int>& ar1, vector<int>& ar2, vector<int>& ar3) 
{

    int i = 0, j = 0, k = 0;
    int n1 = ar1.size();
    int n2 = ar2.size();

    while (i < n1 && j < n2) 
    {
      
        if (ar1[i] < ar2[j])
            ar3[k++] = ar1[i++];
        else
            ar3[k++] = ar2[j++];
    }

    while (i < n1)
        ar3[k++] = ar1[i++];

    while (j < n2)
        ar3[k++] = ar2[j++];
}

int main() 
{
    vector<int> arr1 = {1, 2, 3, 4, 4, 5};
    vector<int> arr2 = {6, 6, 7, 8, 9};

    vector<int> arr3(arr1.size() + arr2.size());

    solution_1 (arr1, arr2, arr3);

    for (int i = 0; i < arr3.size(); i++)
        cout << arr3[i] << " ";

    cout << endl;
    
    solution_2 (arr1, arr2, arr3);

    for (int i = 0; i < arr3.size(); i++)
        cout << arr3[i] << " ";

    return 0;
}

Output

1 2 3 4 4 5 6 6 7 8 9 
1 2 3 4 4 5 6 6 7 8 9