Introduction
In this blog, we will discuss the problem of merging two unsorted arrays into a single sorted array. For this, we will have a look and understand the following two approaches:
- Brute force: We first store all the elements into the final array and then sort the array.
- Two pointers: Here, we first individually sort the two arrays and then, using two pointers, store them in the final array.
Two pointers: The two-pointer technique uses two variables for iterating over array/arrays. Here, it assumes that the array we are traversing over is sorted. This technique is widely used for finding pairs of elements with a given sum. In this problem, we have used this technique over two different arrays to store the elements of these arrays in a sorted manner.
Problem Statement
The problem above states that given two unsorted arrays, we have to merge them into a single sorted array.
Sample Example
Input 1:
a[] = {2,5,4,7}
b[] = {1,6,3}
Output 1:
Merged list: {1,2,3,4,5,6,7}
Explanation:
In the above example, we see that the final array is sorted.
Input 2:
a[] = {1,100,2}
b[] = {2,21,3}
Output 2:
Merged List: {1,2,2,3,21,100}
Explanation:
In the above example, we see that the final array (Merged List) is sorted.Brute Force Approach
In the brute force approach, we first store all the elements in a temp array, then sort them. Below is the solution:
- Create a temp array.
- Store all the elements in this array.
- Sort the array.
Pseudocode
temp[n+m]
k = 0
for i = 1 to n:
temp[k] = a[i]
k+=1
for j = 1 to m:
temp[k] = b[j]
k+=1
sort(temp, temp + n + m)
Implementation in C++
#include "bits/stdc++.h"
using namespace std;
void solve()
{
//Defining the 2 arrays
int a[] = {2,5,4,7};
int b[] = {1,6,3};
int n = sizeof(a)/sizeof(int);
int m = sizeof(b)/sizeof(int);
//Creating a temp array
int temp[n+m];
int k = 0;
//Storing elements from first array in temp
for(auto i: a){
temp[k]=i;k+=1;
}
//Storing elements from second array in temp
for(auto i: b){
temp[k]=i;k+=1;
}
//Sorting the temp array
sort(temp, temp+n+m);
cout<<"Merged List: ";
for(auto i: temp){
cout<<i<<" ";
}
}
int main()
{
solve();
return 0;
}
Output:
Merged List: 1 2 3 4 5 6 7
Implementation in Python
def solve(a,b):
n = len(a)
m = len(b)
#First, we define our array.
temp = [0 for i in range(n+m)]
k = 0
#Storing the elements of both these array into the final array
for i in a:
temp[k] = i
k+=1
for j in b:
temp[k] = j
k+=1
#Sorting the final array.
temp.sort()
#Printing the final array.
print("Merged List: ")
for i in temp:
print(i, end = " ")
# Driver code
a = [ 2,5,4,7]
b = [1,6,3]
solve(a,b)
Output:
Merged List: 1 2 3 4 5 6 7
Complexity Analysis
Time complexity: O((n+m) * log (n+m))
Explanation: From the above solution, we see that:
- First, we store all the elements from both arrays in the temp array. This takes O(n+m) time.
- Sort the final array, i.e., the temp array. This takes O((n+m)*log(n+m)).
Therefore, the total time complexity becomes O((n+m)*log(n+m)) + O(n+m), which equals to
O((n+m)*log(n+m)).
Space complexity: O(n+m)
Explanation: As in the above approach, we had created a temp array to store the final sorted sequence of elements. Therefore, the space complexity of the above array becomes O(n+m).
Also Read - Selection Sort in C
85+ registered