# Merge two sorted arrays in C++

Written By -

## 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 < arr1Size && ptr2 < arr2Size){
if(arr1[ptr1] > arr2[ptr2]){
swap(arr1[ptr1], arr2[ptr2]);
sort(arr2, arr2+arr2Size);
}
ptr1++;
}

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

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 > 1){
ptr1 = 0;
ptr2 = gap-1;

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

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

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

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

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)

Related Posts:

Online Compilers