# Merge two Sorted Arrays Without Extra Space

Problem statement: Given two sorted arrays arr1[] and arr2[] of sizes n and m in non-decreasing order. Merge them in sorted order. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.

Examples:

```Example 1:

Input:
n = 4, arr1[] = [1 4 8 10]
m = 5, arr2[] = [2 3 9]

Output:
arr1[] = [1 2 3 4]
arr2[] = [8 9 10]

Explanation:
After merging the two non-decreasing arrays, we get, 1,2,3,4,8,9,10.

Example2:

Input:
n = 4, arr1[] = [1 3 5 7]
m = 5, arr2[] = [0 2 6 8 9]

Output:
arr1[] = [0 1 2 3]
arr2[] = [5 6 7 8 9]

Explanation:
After merging the two non-decreasing arrays, we get, 0 1 2 3 5 6 7 8 9.
```

### Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution1: Brute Force-

Intuition: We can use a new array of size n+m and put all elements of arr1 and arr2 in it, and sort it. After sorting it, but all the elements in arr1 and arr2.

Approach:

• Make an arr3 of size n+m.
• Put elements arr1 and arr2 in arr3.
• Sort the arr3.
• Now first fill the arr1 and then fill remaining elements in arr2. Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;
void merge(int arr1[], int arr2[], int n, int m) {
int arr3[n+m];
int k = 0;
for (int i = 0; i < n; i++) {
arr3[k++] = arr1[i];
}
for (int i = 0; i < m; i++) {
arr3[k++] = arr2[i];
}
sort(arr3,arr3+m+n);
k = 0;
for (int i = 0; i < n; i++) {
arr1[i] = arr3[k++];
}
for (int i = 0; i < m; i++) {
arr2[i] = arr3[k++];
}

}
int main() {
int arr1[] = {1,4,7,8,10};
int arr2[] = {2,3,9};
cout<<"Before merge:"<<endl;
for (int i = 0; i < 5; i++) {
cout<<arr1[i]<<" ";
}
cout<<endl;
for (int i = 0; i < 3; i++) {
cout<<arr2[i]<<" ";
}
cout<<endl;
merge(arr1, arr2, 5, 3);
cout<<"After merge:"<<endl;
for (int i = 0; i <5; i++) {
cout<<arr1[i]<<" ";
}
cout<<endl;
for (int i = 0; i < 3; i++) {
cout<<arr2[i]<<" ";
}

}

``````

Output:

Before merge:
1 4 7 8 10
2 3 9
After merge:
1 2 3 4 7
8 9 10

Time complexity: O(n*log(n))+O(n)+O(n)

Space Complexity: O(n)

## Java Code

``````import java.util.*;

public class tuf {

public static void main(String[] args) {
int arr1[] = {1,4,7,8,10};
int arr2[] = {2,3,9};
System.out.println("Before merge:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println();
merge(arr1, arr2, arr1.length, arr2.length);
System.out.println("After merge:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}

}
static void merge(int[] arr1, int arr2[], int n, int m) {
int arr3[] = new int[n + m];
int k = 0;
for (int i = 0; i < n; i++) {
arr3[k++] = arr1[i];
}
for (int i = 0; i < m; i++) {
arr3[k++] = arr2[i];
}
Arrays.sort(arr3);
k = 0;
for (int i = 0; i < n; i++) {
arr1[i] = arr3[k++];
}
for (int i = 0; i < m; i++) {
arr2[i] = arr3[k++];
}

}
}
``````

Output:

Before merge:
1 4 7 8 10
2 3 9
After merge:
1 2 3 4 7
8 9 10

Time complexity: O(n*log(n))+O(n)+O(n)

Space Complexity: O(n)

Solution 2: Without using space-

Intuition: We can think of Iterating in arr1 and whenever we encounter an element that is greater than the first element of arr2, just swap it. Now rearrange the arr2 in a sorted manner, after completion of the loop we will get elements of both the arrays in non-decreasing order.

Approach:

• Use a for loop in arr1.
• Whenever we get any element in arr1 which is greater than the first element of arr2,swap it.
• Rearrange arr2.
• Repeat the process. Code:

## C++ Code

``````#include<bits/stdc++.h>

using namespace std;
void merge(int arr1[], int arr2[], int n, int m) {
// code here
int i, k;
for (i = 0; i < n; i++) {
// take first element from arr1
// compare it with first element of second array
// if condition match, then swap
if (arr1[i] > arr2) {
int temp = arr1[i];
arr1[i] = arr2;
arr2 = temp;
}

// then sort the second array
// put the element in its correct position
// so that next cycle can swap elements correctly
int first = arr2;
// insertion sort is used here
for (k = 1; k < m && arr2[k] < first; k++) {
arr2[k - 1] = arr2[k];
}
arr2[k - 1] = first;
}
}
int main() {
int arr1[] = {1,4,7,8,10};
int arr2[] = {2,3,9};
cout << "Before merge:" << endl;
for (int i = 0; i < 5; i++) {
cout << arr1[i] << " ";
}
cout << endl;
for (int i = 0; i < 3; i++) {
cout << arr2[i] << " ";
}
cout << endl;
merge(arr1, arr2, 5, 3);
cout << "After merge:" << endl;
for (int i = 0; i < 5; i++) {
cout << arr1[i] << " ";
}
cout << endl;
for (int i = 0; i < 3; i++) {
cout << arr2[i] << " ";
}

}``````

Output:

Before merge:
1 4 7 8 10
2 3 9
After merge:
1 2 3 4 7
8 9 10

Time complexity: O(n*m)

Space Complexity: O(1)

## Java Code

``````public class tuf {

public static void main(String[] args) {
int arr1[] = {1,4,7,8,10};
int arr2[] = {2,3,9};
System.out.println("Before merge:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println();
merge(arr1, arr2, arr1.length, arr2.length);
System.out.println("After merge:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}

}
static void merge(int[] arr1, int arr2[], int n, int m) {
// code here
int i, k;
for (i = 0; i < n; i++) {
// take first element from arr1
// compare it with first element of second array
// if condition match, then swap
if (arr1[i] > arr2) {
int temp = arr1[i];
arr1[i] = arr2;
arr2 = temp;
}

// then sort the second array
// put the element in its correct position
// so that next cycle can swap elements correctly
int first = arr2;
// insertion sort is used here
for (k = 1; k < m && arr2[k] < first; k++) {
arr2[k - 1] = arr2[k];
}
arr2[k - 1] = first;
}
}
}
``````

Output:

Before merge:
1 4 7 8 10
2 3 9
After merge:
1 2 3 4 7
8 9 10

Time complexity: O(n*m)

Space Complexity: O(1)

Solution 3: Gap method-

Approach:

• Initially take the gap as (m+n)/2;
• Take as a pointer1 = 0 and pointer2 = gap.
• Run a oop from pointer1 &  pointer2 to  m+n and whenever arr[pointer2]<arr[pointer1], just swap those.
• After completion of the loop reduce the gap as gap=gap/2.
• Repeat the process until gap>0.  Code:

## C++ Code

``````
#include<bits/stdc++.h>
using namespace std;
void merge(int ar1[], int ar2[], int n, int m) {
// code here
int gap = ceil((float)(n + m) / 2);
while (gap > 0) {
int i = 0;
int j = gap;
while (j < (n + m)) {
if (j < n && ar1[i] > ar1[j]) {
swap(ar1[i], ar1[j]);
} else if (j >= n && i < n && ar1[i] > ar2[j - n]) {
swap(ar1[i], ar2[j - n]);
} else if (j >= n && i >= n && ar2[i - n] > ar2[j - n]) {
swap(ar2[i - n], ar2[j - n]);
}
j++;
i++;
}
if (gap == 1) {
gap = 0;
} else {
gap = ceil((float) gap / 2);
}
}
}
int main() {
int arr1[] = {1,4,7,8,10};
int arr2[] = {2,3,9};
cout << "Before merge:" << endl;
for (int i = 0; i < 5; i++) {
cout << arr1[i] << " ";
}
cout << endl;
for (int i = 0; i < 3; i++) {
cout << arr2[i] << " ";
}
cout << endl;
merge(arr1, arr2, 5, 3);
cout << "After merge:" << endl;
for (int i = 0; i < 5; i++) {
cout << arr1[i] << " ";
}
cout << endl;
for (int i = 0; i < 3; i++) {
cout << arr2[i] << " ";
}

}``````

Output:

Before merge:
1 4 7 8 10
2 3 9
After merge:
1 2 3 4 7
8 9 10

Time complexity: O(n+m)

Space Complexity: O(1)

## Java Code

``````import java.util.*;
class TUF{
static void swap(int a,int b)
{
int temp=a;
a=b;
b=temp;
}
static void merge(int ar1[], int ar2[], int n, int m) {
// code here
int gap =(int) Math.ceil((double)(n + m) / 2.0);
while (gap > 0) {
int i = 0;
int j = gap;
while (j < (n + m)) {
if (j < n && ar1[i] > ar1[j]) {
swap(ar1[i], ar1[j]);
} else if (j >= n && i < n && ar1[i] > ar2[j - n]) {
swap(ar1[i], ar2[j - n]);
} else if (j >= n && i >= n && ar2[i - n] > ar2[j - n]) {
swap(ar2[i - n], ar2[j - n]);
}
j++;
i++;
}
if (gap == 1) {
gap = 0;
} else {
gap =(int) Math.ceil((double) gap / 2.0);
}
}
}
public static void main(String[] args) {
int arr1[] = {1,4,7,8,10};
int arr2[] = {2,3,9};
System.out.println("Before merge:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println();
merge(arr1, arr2, arr1.length, arr2.length);
System.out.println("After merge:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}

}
}``````

Output:

Before merge:
1 4 7 8 10
2 3 9
After merge:
1 2 3 4 7
8 9 10

Time complexity: O(n+m)

Space Complexity: O(1)