Arrays: Merge sorted array inplace

Problem Statement:

You are given with 2 sorted arrays, you need to merge the array in-place.

You may assume that the first array will have enough space to accomodate all the array elements.

Example:

Input:

arr1 = [1,2,3]
arr2 = [2,5,6]

Output: [1,2,2,3,5,6]

According to the question, we can assume that the first array will have enough space to hold total (m+n) array elements.

So arr1 = [1, 2, 3, 0, 0, 0]

The solution to this problem is very simple, below are the steps on how to do it.

We will have to do a reverse sorting, by taking the max element from arr2 and comparing with the elements from arr1.

We have:

arr1 = [1,2,3,0,0,0], m = 3
arr2 = [2,5,6], n = 3

k = m+n-1

Pass 1:
arr1 = [1,2,3,0,0,0]
            |     |
            i     k

arr2 = [2,5,6]
            |
            j

Now check: arr2[j]>arr1[i] thus arr1[k] = 6. Now decrement both k and j.

At the end of Pass 1, array 1 will look like:

arr1 = [1,2,3,0,0,6]
            |   |
            i   k

Pass 2:

arr1 = [1,2,3,0,0,6]
            |   |
            i   k

arr2 = [2,5,6]
          |
          j

arr2[j]>arr1[i] thus arr1[k] = 5.  Now decrement both k and j.

At the end of Pass 2, array 1 will look like:

arr1 = [1,2,3,0,5,6]
            | |
            i k

Pass 3:

arr1 = [1,2,3,0,5,6]
            | |
            i k

arr2 = [2,5,6]
        |
        j

Now check: arr2[j]>arr1[i] false, so we copy the i'th element in k'th position. Now decrement both k and i.
      
At the end of Pass 2, array 1 will look like:

arr1 = [1,2,3,3,5,6]
          | |
          i k

Pass 4:

arr1 = [1,2,3,3,5,6]
          | |
          i k

arr2 = [2,5,6]
        |
        j

Now check: arr2[j]>arr1[i] thus arr1[k] = 2. Now decrement both k and j.

Final array:

arr1 = [1,2,2,3,5,6]

The time complexity will be  O(m+n).

Solution in C++

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

using namespace std;  


void in_place_merge(vector<int>& arr1, int m, vector<int>& arr2, int n) 
{
  int i = m-1;
  int j = n-1;
  int k = m+n-1;

  while(i>=0&&j>=0)
  {
      if(arr1[i]>arr2[j])
      {
          arr1[k] = arr1[i];
          i--;
          k--;
      }
      else
      {
          arr1[k] = arr2[j];
          j--;
          k--;
      }
  }

  while(i>=0)
      arr1[k--]=arr1[i--];
  while(j>=0)
      arr1[k--]=arr2[j--];
}

int main() 
{ 
    std::vector<int> arr1 = {1, 2, 3, 0, 0, 0}; 
    std::vector<int> arr2 = {2, 5, 6}; 

    in_place_merge(arr1, 3, arr2, 3); 

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

      for (std::vector<int>::iterator itr = arr1.begin(); itr != arr1.end(); ++itr)
      {
         cout<<*itr;
      }
    return 0; 
}

Output:

The sorted array is
122356