Searching and Sorting: Merge 2 sorted arrays

Problem Statement:

You are given two sorted arrays x[] and y[] of size m and n,
You need to merge elements of array x[] to y[] by maintaining sorted order.

Example

Input: arr1[] = {20};
arr2[] = {5, 6};
Output: arr1[] = {5}
arr2[] = {6, 20}

Solution

The solution is very simple, we begin from the last element of arr2[] and search in arr1[].

If there is an element greater in arr1[], then we move the last element of arr1[] to arr2[].

So keep arr1[] and arr2[] sorted, we need to place the last element of arr2[] at the correct place of arr1[].

Time complexity is O(m *n)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;


void merge_two_arrays(int arr1[], int arr2[], int m, int n)
{

    for (int i = n - 1; i >= 0; i--) 
    {
        
        int j;
        int last = arr1[m - 1];

        for (j = m - 2; j >= 0 && arr1[j] > arr2[i]; j--)
        {
            arr1[j + 1] = arr1[j];
         }
 
        if (j != m - 2 || last > arr2[i]) 
        {
            arr1[j + 1] = arr2[i];
            arr2[i] = last;
        }
    }
}
 
int main()
{
    int arr1[] = { 1, 5, 9, 10 };
    int arr2[] = { 2, 3, 8 };
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    merge_two_arrays(arr1, arr2, m, n);
 
    cout << "After Merging First Array: ";
    for (int i = 0; i < m; i++)
        cout << arr1[i] << " ";
    cout << "\nSecond Array: ";
    for (int i = 0; i < n; i++)
        cout << arr2[i] << " ";
    return 0;
}

Output:

After Merging First Array: 1 2 3 5

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *