# Merge two sorted arrays without using additional memory

We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the second array.

For instance, if your two arrays are $A=[1,3,9,14]$ and $B=[2,4,15]$, the result should be $A=[1,2,3,4], B=[9,14,15]$. Entries are integers, and you can use only $O(1)$ extra memory for auxiliary variables.

• Just to clarify, if your two arrays are $A=[1,3,9,14]$ and $B=[2,4,15]$, should the result be $A=[1,2,3,4], B=[9,14,15]$? Also, are the entries integers? Can you use an auxiliary variable for swapping? – Rick Decker Jan 15 '16 at 16:12
• Yes, The values are integers. You can use with only with constant memory. – Guy Kahlon Jan 15 '16 at 16:15
• This has been answered here. As the commentary indicates, the details are a bit hairy. – Rick Decker Jan 15 '16 at 17:12
• Very closely related question. Community, is this a duplicate? – Raphael Jan 17 '16 at 16:20
• @Raphael I have tried to create a virtual array with length that equal to the array1's length + array2's length then merge the virtual array with regular QuickSort, But this solution feel very cumbersome. – Guy Kahlon Jan 17 '16 at 16:24

Here, great solution, from: http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

Below is C++ implementation of above algorithm.

// C++ program for implementation of Sieve of Atkin
#include <bits/stdc++.h>
using namespace std;

// Merge ar1[] and ar2[] with O(1) extra space
void merge(int ar1[], int ar2[], int m, int n)
{
// Iterate through all elements of ar2[] starting from
// the last element
for (int i=n-1; i>=0; i--)
{
/* Find the smallest element greater than ar2[i]. Move all
elements one position ahead till the smallest greater
int j, last = ar1[m-1];
for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
ar1[j+1] = ar1[j];

// If there was a greater element
if (j != m-1)
{
ar1[j+1] = ar2[i];
ar2[i] = last;
}
}
}

• Code-only answers are not a good fit for this site. What are the ideas? Why does it work? Code should be pseudocode at most. – Raphael Jan 17 '16 at 16:17
• @Raphael actually you right I'll update my answer, Thanks for your comment. – Guy Kahlon Jan 17 '16 at 16:19