Arrays: Merge Two Sorted arrays without using extra space

You are given 2 sorted arrays, merge and sort the two arrays in such a way that the initial numbers are in the first array other will be in the next array,

Example:

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

Now, the combined sorted array will be {4, 5, 20}

As arr1 has only 1 element, “4” will be going to the first array, rest all the elements will go to the next array.

Output: arr1[] = {4}
arr2[] = {5, 20}

Solution is very simple, it is very much like insertion sort.

In the solution we compare all the elements of arr1 with the 1st element of arr2.

If the element from arr2 is greater than the element at index arr1, then we swap the elements.

After that we sort the arr2. Then again we shall start the comparing the current index of arr1 with the 1st element of arr2 and follow the same procedure.

Pseudo code:

void merge(int arr1[], int n, int arr2[],  int m)
{
 for (int i = 0; i < n; i++)
 {
  bool flag = 0;
  if (arr1[i] > arr2[0])
  {
   flag = 1;
   swap(arr1[i], arr2[0]);
  }
  if (flag)
  {
   sort(arr2, arr2 + m);
  }
 }
}

The time complexity is O(n∗m)

Solution in C++

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

using namespace std;  


void merge(int arr1[],  int n, int arr2[], int m)
{
 for (int i = 0; i < n; i++)
 {
  bool flag = 0;
  if (arr1[i] > arr2[0])
  {
   flag = 1;
   swap(arr1[i], arr2[0]);
  }
  if (flag)
  {
   sort(arr2, arr2 + m);
  }
 }
}

int main() 
{ 
    int arr1[] = {1, 2, 3}; 
    int arr2[] = {2, 5, 6}; 

    merge(arr1, 3, arr2, 3); 

    cout<<"The sorted array 1 is "<<endl;

      for (int i = 0; i< 3; i++)
      {
         cout<<arr1[i]<<" ";
      }

      cout<<endl<<"The sorted array 2 is "<<endl;

      for (int i = 0; i< 3; i++)
      {
         cout<<arr2[i]<<" ";
      }

    return 0; 
}

Output:

The sorted array 1 is
1 2 2
The sorted array 2 is
3 5 6