Problem Statement:
You are given two sorted arrays x[] and y[] of size m and n,
You need to merge elements of array x[] to y[] by maintaining sorted order.
Example
Input: arr1[] = {20};
arr2[] = {5, 6};
Output: arr1[] = {5}
arr2[] = {6, 20}
Solution
The solution is very simple, we begin from the last element of arr2[] and search in arr1[].
If there is an element greater in arr1[], then we move the last element of arr1[] to arr2[].
So keep arr1[] and arr2[] sorted, we need to place the last element of arr2[] at the correct place of arr1[].
Time complexity is O(m *n)
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream>
using namespace std;
void merge_two_arrays(int arr1[], int arr2[], int m, int n)
{
for (int i = n - 1; i >= 0; i--)
{
int j;
int last = arr1[m - 1];
for (j = m - 2; j >= 0 && arr1[j] > arr2[i]; j--)
{
arr1[j + 1] = arr1[j];
}
if (j != m - 2 || last > arr2[i])
{
arr1[j + 1] = arr2[i];
arr2[i] = last;
}
}
}
int main()
{
int arr1[] = { 1, 5, 9, 10 };
int arr2[] = { 2, 3, 8 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
merge_two_arrays(arr1, arr2, m, n);
cout << "After Merging First Array: ";
for (int i = 0; i < m; i++)
cout << arr1[i] << " ";
cout << "\nSecond Array: ";
for (int i = 0; i < n; i++)
cout << arr2[i] << " ";
return 0;
}
Output:
After Merging First Array: 1 2 3 5