In this article, we will write a program to merge two unsorted arrays. The output is the sorted array in ascending order.
Input : a = {10, 5, 15}
b = {20, 3, 2}
Output : The merged array in sorted order {2, 3, 5, 10, 15, 20}
Input : a = {1, 10, 5, 15}
b = {20, 0, 2}
Output : The merged array in sorted order {0, 1, 2, 5, 10, 15, 20}
Approach 1
The first approach that can be used here is to concatenate both the arrays and sort the concatenated array. We create a third array of the size of the first two arrays and then transfer all the elements of both the arrays into the resultant array. After the append operation, we sort the resultant array.
C code
#include <bits/stdc++.h>
using namespace std;
void sortedMerge(int a[], int b[], int res[],
int n, int m) // Merge two arrays in unsorted manner
{
// Concatenate two arrays
int i = 0, j = 0, k = 0;
while (i < n) { // iterate in first array
res[k] = a[i]; // put each element in res array
i += 1;
k += 1;
}
while (j < m) { // iterate in the second array
res[k] = b[j]; // put each element in res array
j += 1;
k += 1;
}
sort(res, res + n + m); // sort the res array to get the sorted Concatenate
}
int main()
{
int a[] = { 10, 5, 15, 22, 100 };
int b[] = { 20, 3, 2, 12, 1, 7 };
int n = sizeof(a) / sizeof(a[0]); // find the size of array a
int m = sizeof(b) / sizeof(b[0]); // find the size of array b
int res[n + m]; // create res array to Concatenate both the array
sortedMerge(a, b, res, n, m); // call function to append and sort
cout << "The sorted array is: ";
for (int i = 0; i < n + m; i++)
cout << " " << res[i];
cout << "\n";
return 0;
}
Output
The sorted array is: 1 2 3 5 7 10 12 15 20 22 100
Time complexity
O((n+m)log(n+m), where n and m are the sizes of the arrays
Space complexity
O(n+m)
Approach 2
The above approach can be optimised when we use the idea of first sorting then merging it to the third array. Sort both the arrays separately and merge them into the resultant array.
C code
// CPP program to merge two unsorted lists
// in sorted order
#include <bits/stdc++.h>
using namespace std;
void sortedMerge(int a[], int b[], int res[],
int n, int m) // Merge two arrays in unsorted manner
{
sort(a, a + n); // Sort the array a
sort(b, b + m); // sort the array b
int i = 0, j = 0, k = 0;
while (i < n && j < m) { // After the array are sorted compare and merge to third array
if (a[i] <= b[j]) { // if element of a is less than b
res[k] = a[i]; // put element of a into the res and increment i
i += 1;
k += 1;
} else {
res[k] = b[j]; // otherwise put the element of b into the res array and increment j
j += 1;
k += 1;
}
}
while (i < n) { // If array a elements are left in the array put in res
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m) { // If array a elements are left in the array put in res
res[k] = b[j];
j += 1;
k += 1;
}
}
int main()
{
int a[] = { 10, 5, 15, 22, 100 };
int b[] = { 20, 3, 2, 12, 1, 7 };
int n = sizeof(a) / sizeof(a[0]); // find the size of array a
int m = sizeof(b) / sizeof(b[0]); // find the size of array b
int res[n + m]; // create res array to Concatenate both the array
sortedMerge(a, b, res, n, m); // call function to append and sort
cout << "The sorted array is: ";
for (int i = 0; i < n + m; i++)
cout << " " << res[i];
cout << "\n";
return 0;
}
Output
The sorted array is: 1 2 3 5 7 10 12 15 20 22 100
Time Complexity:
O (nlogn + mlogm + (n + m)) // which is far better than approach 1
Space Complexity:
O ( (n + m) ) It remains same as the approach 1