Merge Two Unsorted Arrays

Approach-2

The above method can be improved by sorting first and then combining it with the third array. Separately sort both arrays before merging them into the final array.

C++ Code

#include <bits/stdc++.h>  
using namespace std;  
// Function for Merge two arrays in unsorted manner
void sortedMerge(int a[], int b[], int res[],  
    int n, int m)   
{  
    sort(a, a + n); // sorting array a   
    sort(b, b + m); // sorting array b   
  
  
    int i = 0, j = 0, k = 0; 
    // After sorting, compare and merge elements to third array
    while (i < n && j < m) {    
        if (a[i] <= b[j]) {    
            res[k] = a[i];    
            i += 1;  
            k += 1;  
        } 
        else 
        {
            // otherwise putting the elements of b into res array and incrementing j
            res[k] = b[j]; 
            j += 1;  
            k += 1;  
        }  
    } 
    // If array a elements are left putting them in res 
    while (i < n) {  
        res[k] = a[i];  
        i += 1;  
        k += 1;  
    }  
    while (j < m) { // If array b elements are left putting them in res  
        res[k] = b[j];  
        j += 1;  
        k += 1;  
    }  
}  
  
int main()  
{  
    int a[] = { 50, 95, 35, 12, 100 };  
    int b[] = { 10, 43, 23, 33, 9, 17 };  
    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;  
}  

You can also try this code with Online C++ Compiler

Run Code

Output

The sorted array is:  9 10 12 17 23 33 35 43 50 95 100

You can also try this code with Online C++ Compiler

Run Code

Time Complexity: O (nlogn + mlogm + (n + m)) it is better than approach 1

Space Complexity: O ( (n + m) ) It remains same as approach 1

You can try by yourself with the help of online C++ Compiler.

Also read - Decimal to Binary c++

FAQs

1. What is logarithmic(log) time complexity?
   Since each extra piece of data takes less time to process than the previous one, logarithmic complexity means that the time to finish rises more slowly than the input size: to raise the runtime by a constant amount, you must increase the input size exponentially.
    
2. What do you mean by linear time complexity in data structures?
   The time to finish is generally proportional to the input quantity. Each extra bit of input causes, a constant rise in runtime since each additional bit of information takes roughly the same amount of time to process.

Key Takeaways

In this article, we have extensively discussed the program to merge two unsorted arrays using two approaches. We tried to cover it with some examples.

You can look at more exciting blogs and articles curated by the coding ninja's team by visiting Library.

We hope that this blog has helped you enhance your knowledge regarding Merging arrays in C++ and if you would like to learn more, check out our articles on Arrays in C++. 

Recommended Problem - Merge K Sorted Arrays

Do upvote our blog to help other ninjas grow. 

Happy Coding!