{"post":"

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>\nusing namespace std;\nvoid mergeTwoSortedArrays(int arr1[], int arr2[], int arr1Size, int arr2Size){\nint ptr1 = 0,\nptr2 = 0;
\nwhile(ptr1 &lt; arr1Size && ptr2 &lt; arr2Size){\n\tif(arr1[ptr1] &gt; arr2[ptr2]){\n    \tswap(arr1[ptr1], arr2[ptr2]);\n      \tsort(arr2, arr2+arr2Size);\n    }\n  \tptr1++;\n\t}\n\ncout&lt;&lt;\"Array 1 after sorting \"&lt;&lt;endl;\nfor(int i = 0; i &lt; arr1Size; i++){\n\t\tcout&lt;&lt;arr1[i]&lt;&lt;\" \";\n\t}\ncout&lt;&lt;endl&lt;&lt;\"Array 2 after sorting \"&lt;&lt;endl;\nfor(int i = 0; i &lt; arr2Size; i++){\n\t\tcout&lt;&lt;arr2[i]&lt;&lt;\" \";\n\t}\n
\n}
\nint main(){\nint arr1[] = {1,3,4,5};\nint arr2[] = {2,4,6,8};\nint arr1Size = sizeof(arr1)/sizeof(arr1[0]);\nint arr2Size = sizeof(arr2)/sizeof(arr2[0]);\nmergeTwoSortedArrays(arr1, arr2, arr1Size, arr2Size);\nreturn 0;\n}

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>\nusing namespace std;\nvoid mergeTwoSortedArrays(int arr1[], int arr2[], int arr1Size, int arr2Size){\nint ptr1 = 0,\nptr2 = 0,\ngap  = ((arr1Size + arr2Size) / 2) + ((arr1Size + arr2Size) % 2);
\nwhile(gap &gt; 1){\n  \tptr1 = 0;\n  \tptr2 = gap-1;\n  \t\n  \t//if both ptr are in first array\n\twhile(ptr2 &lt; arr1Size ){\n      if(arr1[ptr1] &gt; arr1[ptr2]){\n          swap(arr1[ptr1], arr1[ptr2]);\n      }\n      ptr1++;\n      ptr2++;\n    }\n  \t\n  \t//if one ptr are in first array and other in second\n  \tptr2 = 0;\n\twhile(ptr1 &lt; arr1Size && ptr2 &lt; arr2Size){\n      if(arr1[ptr1] &gt; arr2[ptr2]){\n          swap(arr1[ptr1], arr2[ptr2]);\n      }\n      ptr1++;\n      ptr2++;\n    }\n  \t\n  \tptr1 = 0;\n  \t//if both are in second array\n  \twhile(ptr2 &lt; arr2Size){\n      if(arr2[ptr1] &gt; arr2[ptr2]){\n          swap(arr2[ptr1], arr2[ptr2]);\n      }\n      ptr1++;\n      ptr2++;\n    }\n  \tgap  = (gap/2) + (gap % 2);\n}\n\ncout&lt;&lt;\"Array 1 after sorting \"&lt;&lt;endl;\nfor(int i = 0; i &lt; arr1Size; i++){\n\tcout&lt;&lt;arr1[i]&lt;&lt;\" \";\n}\ncout&lt;&lt;endl&lt;&lt;\"Array 2 after sorting \"&lt;&lt;endl;\nfor(int i = 0; i &lt; arr2Size; i++){\n\tcout&lt;&lt;arr2[i]&lt;&lt;\" \";\n}\n
\n}
\nint main(){\nint arr1[] = {1,3,4,5};\nint arr2[] = {2,7,6,8,9};\nint arr1Size = sizeof(arr1)/sizeof(arr1[0]);\nint arr2Size = sizeof(arr2)/sizeof(arr2[0]);\nmergeTwoSortedArrays(arr1, arr2, arr1Size, arr2Size);\nreturn 0;\n}

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

SC – O(1)

\n","title":"Merge two sorted arrays in C++","authorDetails":{"name":"Ankita Khan","slug":"ankita-khan"},"seo":{"title":"Merge two sorted arrays in C++"},"description":"Merge two sorted arrays using C++. The input contains two sorted arrays and the output is the merged resultant of these two arrays.","slug":"merge-two-sorted-arrays/","articleId":"636a83447bb1ce5072622b86","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}