Merge two Sorted Arrays in C, C++

Write a C, C++ program to merge two sorted arrays. Given a two sorted arrays, Write a program to  merge these sorted arrays and print the final result.

In this post, i'll show you how to merge two sorted arrays with the help of a third array.

Reverse an Array Using Recursion

Insert an Element in an Array

Sorting Algorithm and their time complexity

Program Logic

Let's declare two variables P and Q.

P = Length of arr1.
Q = Length of arr2.

While p and q is not equal to zero, we merge the element of arr1 and arr2 in a third array (arr3). But there may be a case, when either the length of arr1 or arr2 is not equal.

while(p && q){
       
       if(arr1[i] < arr2[j]){
           arr3[k++] = arr1[i++];
           p--;
       }else {
           arr3[k++] = arr2[j++];
           q--;
       }
       
   }

/* If length of arr1 is greater than arr2, merge 

   remaining elements of arr1 into arr3 */

while(p > 0){
       arr3[k++] = arr1[i++];
       p--;
   }
 

/* Similarly If length of arr2 is greater than arr1, merge 

   remaining elements of arr2 into arr3 */ 
 

while(q > 0){
       arr3[k++] = arr2[j++];
       q--;
   }

 

C Program to Merge Two Sorted Arrays

#include <stdio.h>

int main(void) {

   int arr1[] = {1,3,6,8,9};
   int arr2[] = {5,6,9,12};
   
   int arr3[100];
   int i = 0,j = 0,k = 0,s;
   
   /* length of arr1 */
   
   int p = sizeof(arr1)/sizeof(arr1[0]);
   
   /*length of arr2 */
   
   int q = sizeof(arr2)/sizeof(arr2[0]);
   
   /* While p and q is not equal to zero */
   
   while(p && q)
   {
       
       if (arr1[i] < arr2[j])
       {
           arr3[k++] = arr1[i++];
           p--;
           
       } else {
        
           arr3[k++] = arr2[j++];
           q--;
       }
       
   }
   
   while ( p > 0)
   {
       arr3[k++]=arr1[i++];
       p--;
   }
   
   while( q > 0)
   {
       arr3[k++]=arr2[j++];
       q--;
   }
   
   /* After Merging */ 
   
   for( s = 0; s < k; s++)
   {
       printf("%d ",arr3[s]);
   } 
   
 return 0;
}

C++ Program to Merge Two Sorted Arrays

#include <iostream>
using namespace std;

void merge (int arr1[], int arr2[], int len1, int len2) {

        int arr3[200];

        int p = 0;
        int q = 0;
        int k = 0;

        while ( p < len1 && q < len2) {

            if (arr1[p] < arr2[q]) {

                arr3[k++] = arr1[p++];

            } else {

                arr3[k++] = arr2[q++];
                
            }
                
        
        }

        while ( p < len1) {
         
            arr3[k++] = arr1[p++];
            
        }

        while ( q < len2) {
         
            arr3[k++] = arr2[q++];
            
        }

        for ( int c = 0; c < k; c++) {

            cout << arr3[c] << " ";
            
        }
                
}

int main() {

   int arr1[100], arr2[100], len1, len2;

   cout << "Enter the length of first array \n";
   cin >> len1;

   cout << "Enter the length of second array \n";
   cin >> len2;

   cout << "Enter sorted values for first array \n";

   for (int i = 0; i < len1; i++) {

           cin >> arr1[i];

    }

    cout << "Enter sorted values for second array \n";

    for (int j = 0; j < len2; j++) {

        cin >> arr2[j];

    }

    merge(arr1, arr2, len1, len2);

    return 0;
}

Output :

Enter the length of first array  : 3

Enter the length of second array : 3

Enter sorted values for first array :  4  9  10

Enter sorted values for second array : 1  5  7

1     4      5    7    9   10

Programming question on Arrays

Programming question on Strings