Recent Posts

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)

Merge two sorted arrays in C++