In this tutorial, we will develop a script to combine two unsorted arrays. The result will be a sorted array arranged in ascending order.
Input : a = {10, 5, 15}
b = {20, 3, 2}
The combined array is arranged in a sorted manner as follows: {2, 3, 5, 10, 15, 20}
Input : a = {1, 10, 5, 15}
b = {20, 0, 2}
The combined array sorted in ascending order is {0, 1, 2, 5, 10, 15, 20}.
Approach 1
One possible method is to merge the arrays and then sort the merged array. A new array is generated with a length equal to the sum of the lengths of the original arrays. Subsequently, all elements from both arrays are moved to the new array. Following this concatenation, the new array is sorted.
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
The time complexity of the algorithm is O((n+m)log(n+m)), where n and m represent the sizes of the arrays.
Space complexity
O(n+m)
Approach 2
The method mentioned above can be enhanced by incorporating the concept of sorting the arrays individually before merging them into a third array. By sorting both arrays independently and then combining them, we can generate the final array with the sorted elements.
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)) // a more efficient alternative compared to the first approach
Space Complexity:
O ( (n + m) ) It remains same as the approach 1
