Prerequisites:- Reccursion
Problem :- Given two sorted arrays A and B of sizes N and M respectively, the task is to merge these two arrays while maintaining the final array sorted.
Approach:
To solve this problem use the concept of merging two sorted arrays similar to the merge step of Merge Sort.
Algorithm:
Initialize an empty array, let’s call it merged_array, to store the merged result.
Initialize two pointers, i and j, to iterate through arrays A and B respectively.
Compare the elements at indices i and j in arrays A and B respectively.
Append the smaller element to the merged_array.
Increment the corresponding pointer (i or j) of the smaller element.
Repeat steps 3-5 until one of the arrays (A or B) is completely traversed.
After reaching the end of one of the arrays, append the remaining elements of the other array to the merged_array.
Return the merged_array.
Solution :-
C++ Solution : -
#include <iostream>
#include <vector>
using namespace std;
void mergeArrays(const vector<int>& a, const vector<int>& b) {
int n = a.size(), m = b.size();
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] < b[j]) cout << a[i++] << " ";
else cout << b[j++] << " ";
}
while (i < n) cout << a[i++] << " ";
while (j < m) cout << b[j++] << " ";
}
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int& ai : a) cin >> ai;
for (int& bi : b) cin >> bi;
mergeArrays(a, b);
return 0;
}