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 Second Array: 8 9 10