# Merge two sorted arrays in C++

Written by

Ankita Khan

## Merge two sorted arrays Problem

Input: arr1 = {1,3,5,7} and arr2 = {2,4,6,8,10}

Output: arr1 = {1,2,3,4} and arr2 = {5,6,7,8,9,10}

## Brute Force Approach

Take a temporary array and add the values of arr1 and arr2 to it. Then traverse the temp array and put values in the correct order in arr1 and arr2.

TC – O(N+M)

SC – O(N+M)

## Better Brute Force Approach

We’ll take two pointers, one we’ll put on array1 and one on arr2. Now we’ll check if arr1[ptr1] > arr2[ptr2] then we’ll swap them and sort array2.

#include<bits/stdc++.h>
using namespace std;
void mergeTwoSortedArrays(int arr1[], int arr2[], int arr1Size, int arr2Size){
int ptr1 = 0,
ptr2 = 0;
while(ptr1 &lt; arr1Size &amp;&amp; ptr2 &lt; arr2Size){
if(arr1[ptr1] &gt; arr2[ptr2]){
swap(arr1[ptr1], arr2[ptr2]);
sort(arr2, arr2+arr2Size);
}
ptr1++;
}

cout&lt;&lt;"Array 1 after sorting "&lt;&lt;endl;
for(int i = 0; i &lt; arr1Size; i++){
cout&lt;&lt;arr1[i]&lt;&lt;" ";
}
cout&lt;&lt;endl&lt;&lt;"Array 2 after sorting "&lt;&lt;endl;
for(int i = 0; i &lt; arr2Size; i++){
cout&lt;&lt;arr2[i]&lt;&lt;" ";
}

}
int main(){
int arr1[] = {1,3,4,5};
int arr2[] = {2,4,6,8};
int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
mergeTwoSortedArrays(arr1, arr2, arr1Size, arr2Size);
return 0;
}

TC – O(N*M) //linear traversal = N, reordering arr2 = M

SC – O(1)

## Optimal Approach

### Gap method

In this method, we’ll slowly bring the elements closer which should be together in the results.

We’ll take two pointers, the first pointer will come at arr[0] and the second will be at gap i.e (arr1Size + arr2Size / 2), now compare these elements if they are not in correct order swap it. And after the iteration reduce the gap(gap/2).

We have to ceil values so all the possibilities are being checked.

#include<bits/stdc++.h>
using namespace std;
void mergeTwoSortedArrays(int arr1[], int arr2[], int arr1Size, int arr2Size){
int ptr1 = 0,
ptr2 = 0,
gap  = ((arr1Size + arr2Size) / 2) + ((arr1Size + arr2Size) % 2);
while(gap &gt; 1){
ptr1 = 0;
ptr2 = gap-1;

//if both ptr are in first array
while(ptr2 &lt; arr1Size ){
if(arr1[ptr1] &gt; arr1[ptr2]){
swap(arr1[ptr1], arr1[ptr2]);
}
ptr1++;
ptr2++;
}

//if one ptr are in first array and other in second
ptr2 = 0;
while(ptr1 &lt; arr1Size &amp;&amp; ptr2 &lt; arr2Size){
if(arr1[ptr1] &gt; arr2[ptr2]){
swap(arr1[ptr1], arr2[ptr2]);
}
ptr1++;
ptr2++;
}

ptr1 = 0;
//if both are in second array
while(ptr2 &lt; arr2Size){
if(arr2[ptr1] &gt; arr2[ptr2]){
swap(arr2[ptr1], arr2[ptr2]);
}
ptr1++;
ptr2++;
}
gap  = (gap/2) + (gap % 2);
}

cout&lt;&lt;"Array 1 after sorting "&lt;&lt;endl;
for(int i = 0; i &lt; arr1Size; i++){
cout&lt;&lt;arr1[i]&lt;&lt;" ";
}
cout&lt;&lt;endl&lt;&lt;"Array 2 after sorting "&lt;&lt;endl;
for(int i = 0; i &lt; arr2Size; i++){
cout&lt;&lt;arr2[i]&lt;&lt;" ";
}

}
int main(){
int arr1[] = {1,3,4,5};
int arr2[] = {2,7,6,8,9};
int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
mergeTwoSortedArrays(arr1, arr2, arr1Size, arr2Size);
return 0;
}

TC – (N+M)(log(N+M)

SC – O(1)