Merge two sorted arrays in C++

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;

}
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);

}
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)