Sorting: Merge two sorted arrays without extra space.

Problem Statement:

You are given 2 sorted arrays a[] and b[] with size n and m.

You need to merge both the arrays such that, smallest n elements are in a and remaining m elements in b[].

Example:

Input: a[] = [2, 4, 7, 10], b[] = [2, 3]
Output: a[] = [2, 2, 3, 4], b[] = [7, 10] 

Solution 1:

Traverse the b array from the end and compare each element with the end element of a[].

For any index i if b[i] is smaller than the element of a[], replace b[i] with the last element of a[].

To keep a[] sorted, we do it by finding the correct index using inser step concept of insertion sort

To keep b[] sorted, we do it by traversing b[] from end and inset the current element of b[] is smaller

Time Complexity: O(m * n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>

using namespace std;

void solution(vector<int>& a, vector<int>& b) 
{
  	
    for (int i = b.size() - 1; i >= 0; i--) 
    {
      	
        if (a.back() > b[i]) 
        {
          
            int last = a.back();
          	int j = a.size() - 2;
          	
            while (j >= 0 && a[j] > b[i]) 
            {
                a[j + 1] = a[j];
                j--;
            }
          
            a[j + 1] = b[i];
            b[i] = last;
        }
    }
}

int main() 
{
    vector<int> a = {1, 4, 5, 9, 10, 15};
    vector<int> b = {2, 3, 6, 14};

    solution(a, b);

    for (int ele: a)
        cout << ele << " ";
    cout << "\n";
    for (int ele: b)
        cout << ele << " ";
    return 0;
}

Output

1 2 3 4 5 6 
9 10 14 15