# Merge Two Sorted Arrays in-place

Posted in  Vinay Khatri
Last updated on November 14, 2022

## Problem

Two integer arrays ``` nums1 ``` and ``` nums2 ``` are sorted in non-decreasing order, and two integers m and n are supplied representing the number of integers in ``` nums1 ``` and ``` nums2 ``` correspondingly. In a single pass, merge ``` nums1 ``` and ``` nums2 ``` into a single array. The final classified array should be kept inside the array ``` nums1 ``` rather than returned by the function. To do this, ``` nums1 ``` has a length of ``` m + n ``` where the elements of the first ``` m ``` indicate the items of ``` nums1 ``` . The length of ``` nums2 ``` is ``` n ``` .

### Brute force approach

We can copy all the elements of nums2 into nums1 and then sort the entire array. This is an easy yet inefficient solution as this is not in-place and takes O(( m + n )log( m + n )) time.

### Efficient Approach

We can follow a 3 pointers approach. We place one pointer at the ending element of the first array and the second pointer at the ending element of the second array. Let’s say pointers are ``` one ``` and ``` two ``` respectively. The third pointer tells the next available index to place the element. This is initialized to the ``` ( ``` ``` size of nums1 ``` ``` -1) ``` . Let’s call this variable as ``` finish ``` . We then compare these two elements. If ``` nums1 [one] >= nums2 ``` ``` [two] ``` , we  place this element at the last index of ``` nums1 ``` and decrease ``` finish ``` and vice versa. We do this until all the pointers are greater than or equal to 0.   This is an in-place solution and takes O( m + n ) time.

#### C++

```#include <iostream>
#include <algorithm>
using namespace std;
void solve(int a[], int b[], int m, int n)
{

for (int i = 0; i < m; i++)
{

if (a[i] > b)
{
swap(a[i], b);
int first = b;

int k;
for (k = 1; k < n && b[k] < first; k++) {
b[k - 1] = b[k];
}

b[k - 1] = first;
}
}
}

int main()
{
int a[] = { 1, 3, 4, 5 };
int b[] = { 2, 3, 10 };

int m = sizeof(a) / sizeof(a);
int n = sizeof(b) / sizeof(b);

solve(a, b, m, n);

for(int i=0;i<m;i++) cout<<a[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++) cout<<b[i]<<" ";

return 0;
}```

#### Python

```def solve(a, b):

m = len(a)
n = len(b)
for i in range(m):

if a[i] > b:
temp = a[i]
a[i] = b
b = temp

first = b
k = 1
while k < n and b[k] < first:
b[k - 1] = b[k]
k = k + 1

b[k - 1] = first

a = [1, 4, 7, 8, 10]
b = [2, 3, 9]

solve(a, b)

print(a)
print(b)
```

#### C

```void solve(int a[], int b[], int m, int n)
{

for (int i = 0; i < m; i++)
{

if (a[i] > b)
{
int temp = a[i];
a[i]=b;
b=temp;
int first = b;

int k;
for (k = 1; k < n && b[k] < first; k++) {
b[k - 1] = b[k];
}

b[k - 1] = first;
}
}
}

int main()
{
int a[] = { 1, 3, 4, 5 };
int b[] = { 2, 3, 10 };

int m = sizeof(a)/sizeof(a);
int n = sizeof(b)/sizeof(b);

solve(a, b, m, n);

for(int i=0;i<m;i++) printf("%d ",a[i]);
printf("\n");
for(int i=0;i<n;i++) printf("%d ",b[i]);

return 0;
}```

Output

```[1, 2, 3, 4, 7]
[8, 9, 10]```