Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.3.
Implementation in Python
2.4.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.3.
Implementation in Python
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What are the different sorting algorithms that can be used in the above approach?
4.2.
What is a Two pointer technique?
4.3.
What is the difference between sort function used in Python and C++?
5.
Conclusion
Last Updated: Mar 27, 2024

Merging two unsorted arrays in sorted order

Author Akshit Mehra
0 upvote

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:

  1. Brute force: We first store all the elements into the final array and then sort the array.
  2. 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:

  1. Create a temp array.
  2. Store all the elements in this array.
  3. 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:

  1. First, we store all the elements from both arrays in the temp array. This takes O(n+m) time.
  2. 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In the optimized approach, we sort the two given arrays and then merge them both. Below is the procedure:

  1. Sort the two arrays.
  2. Create a temp array. 
  3. Use a two-pointer approach to insert the elements in the temp array. One pointer will correspond to array one and the other to the second array.
  4. Compare element-wise both arrays and correspondingly store the element in temp array.

Pseudocode

sort(a, a + n)
sort(b,b + m)
temp[n+m]
while(i less than n and j less than m):
if a[i] less than b[j]:
temp[k] = a[i]
i++
else:
temp[k] = b[j]
j++
k++


while(i less than n):
temp[k]=a[i]
k++
i++
while(j less than m):
temp[k] = b[j]
j++
k++

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);

    //Sorting both the arrays individually
    sort(a, a+n);
    sort(b, b+m);

    //Creating a temp array to store the final sorted array
    int temp[n+m];
    int i,j,k;i=j=k=0;

    //Now, using 2 pointers over individual arrays to
    //Store the elements in final array in sorted
    //Order
    while(i<n && j<m){
        if(a[i]<b[j]){
            temp[k]=a[i];
            i+=1;
        }else{
            temp[k]=b[j];
            j+=1;
        }k+=1;
    }

    //For case when one of the arrays gets inserted
    //Completely before the other array.
    while(i<n){
        temp[k]=a[i];i+=1;k+=1;
    }
    while(j<m){
        temp[k]=b[j];j+=1;k+=1;
    }
    cout<<"Merged List: ";
    for(auto i: temp){
        cout<<i<<" ";
    }
}  
int main()
{
    solve();
    return 0;
}

 

Output:

Merged List: 1 2 3 4 5 6 7


Also see, Rabin Karp Algorithm

Implementation in Python

def solve(a,b):
    n = len(a)
    m = len(b)
    
    #Sorting the 2 arrays
    a.sort()
    b.sort()
    
    i,j,k = 0,0,0
    
    temp = [0 for i in range(n+m)]
    
    #Using the 2 pointer to now store the elements in individual sorted arrays 
    #into the final array.
    while(i<n and j<m):
        if a[i]<b[j]:
            temp[k]=a[i]
            i+=1
        else:
            temp[k]=b[j]
            j+=1
        k+=1
    
    #If one of the arrays had already been stored in the final array.
    while(i<n):
        temp[k]=a[i]
        i+=1
        k+=1
    
    while(j<m):
        temp[k]=b[j]
        j+=1
        k+=1
    
    #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*log(n) + m*log(m))

Explanation: From the above solution, we see that:

  1. Sorting the first array takes n*log(n) time.
  2. Sorting the second array takes m*log(m) time.

 

Therefore, the total time complexity becomes n*log(n) + m*log(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).

Check out this array problem - Merge 2 Sorted Arrays

Frequently Asked Questions

What are the different sorting algorithms that can be used in the above approach?

Apart from Merge sort, we can use Quicksort in the above problem, as it also gives O(nlog(n)) as its average time complexity. But, if we’ve used Bubble sort, Insertion sort, or selection sort, our time complexity would have become O(n2).

What is a Two pointer technique?

Two pointer technique means that we are using 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.

What is the difference between sort function used in Python and C++?

It is a built-in function of the algorithm header file that is used to organize containers such as arrays and vectors. Internally, Quick-sort is used to implement this function.

Python employs the Timsort algorithm. Timsort is a hybrid sorting algorithm that combines merge sort and insertion sort to produce good results on a wide range of real-world data.

Conclusion

This article discussed the problem of merging two unsorted arrays into a single array that is sorted. Once you are done with this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

Recommended problems -

 

We hope that this blog has helped you increase your knowledge regarding such DSA problems, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"

Previous article
Minimum swaps required to bring all elements together less than or equal to a given number
Next article
MO’s algorithm and its applications
Live masterclass