C++ Program to Merge Two Arrays

This is a C++ Program to Merge Two Arrays in Order.

Problem Description

An array is a collection of elements of the same type placed in contiguous memory locations that can be individually referenced by using an index to a unique identifier. This operation is used to merge two one-dimensional arrays into a third one-dimensional array.

We are given two arrays with their elements and we need to merge these two arrays such that the third array has all the elements of the first and second array with an array being in a sorted state.

Methods for this operation:
To perform this operation we can have two approaches one is Naive Approach i.e. a general approach with time complexity O(n1 * n2) where n1 and n2 are the sizes of the two array. Other is the Merge Sort Algorithm where with the help of Merge() function we will perform the operation with time complexity O(n1 + n2).

Approach One:
Naive Approach with time complexity O(n1 * n2)
Create third array of size n1 + n2.
Copy all n1 elements of the first array to the third array.
Traverse second array and one by one insert elements of the third array to the first array. This step takes O(n1 * n2) time.

Approach Two:
Merge Sort Algorithm with time complexity O(n1 + n1)
Create the third array of size n1 + n2.
Traverse first array and second array simultaneously.
Pick smaller of current elements in first array and second array, copy this smaller element to next position in the third array and move ahead in the third array and the array whose element is picked.
If there are remaining elements in the first array or second array, copy them also in the third array.

Here, we will use a Merge Sorting Algorithm to solve our problem.

Expected Input and Output

Case 1. Both the arrays have unsorted elements.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If the first array has elements = {3, 6, 1}
and second array has elements = {5, 2, 11, 16, 9},
then the output array will be = {1, 2, 3, 5, 6, 9, 11, 16}

Case 2. Both arrays are sorted in ascending order.

If the first array has elements = {2, 4, 6, 8}
and the second array has elements = {1, 3, 5, 7, 9, 11},
then the output array will be = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11}

Case 3. Both the arrays are sorted in descending order.

Check this: C++ Books | Programming MCQs

If the first array contains elements as = {9, 6, 5, 3, 1}
and the second array contains elements as = {21, 14, 9, 4},
then the output array will have elements {1, 3, 4, 5, 6, 9, 9, 14, 21}

Problem Solution

1. Create an array array3[ ] of size n1 + n2.
2. Traverse array1[ ] and array2[ ] simultaneously.
3. Pick smaller of current elements in array1[ ] and array2[ ], copy this smaller element to next position in array3[ ] and move ahead in array3[ ] and the array whose element is picked.
4. If there are remaining elements in array1[ ] or array2[ ], copy them also in array3[ ].

Program/Source Code

Here is the source code of the C++ Program to Merge Two Arrays in Order. The program is successfully compiled and tested using Codeblocks gnu/GCC compiler on Windows 10. The program output is also shown below.

```
/* C++ Program to Merge Two arrays */
```
```
#include <bits/stdc++.h>
```
```
#define N 100
```
```
using namespace std;
```
```
class merge_Array {
```
```
public:
```

    // Merge() function will merge the elements of array1 and array2 in array3.

    void Merge(int array1[N], int array2[N], int array3[N], int n1, int n2)

```
    {
```
```
        int i = 0, j = 0, k = 0;
```
```
        // Traverse both array.
```
```
        while (i < n1 && j < n2)
```
```
        {
```

            /* if element of array1 is smaller then

             * copy the element of array1 in array3

```
             */
```
```
            if (array1[i] < array2[j])
```
```
            {
```

                array3[k++] = array1[i++];

```
            }
```

            /* if element of array2 is small then

             * copy the element of array2 in array3

```
             */
```
```
            else
```
```
            {
```

                array3[k++] = array2[j++];

```
            }
```
```
        }
```

        // Copy remaining elements of first array.

```
        while (i < n1)
```
```
        {
```
```
            array3[k++] = array1[i++];
```
```
        }
```

        // Copy remaining elements of second array

```
        while (j < n2)
```
```
        {
```
```
            array3[k++] = array2[j++];
```
```
        }
```
```
    }
```
```
};
```
```
/*
```
```
 * Main function
```
```
 */
```
```
int main()
```
```
{
```
```
    merge_Array ma;
```
```
    int n1, n2, n3;
```
```
    int i;
```
```
    int A[N], B[N], C[N];
```

    cout << "Enter the size of First array:\n";

```
    cin >> n1;
```

    cout << "\nEnter the elements of First array:\n";

```
    for (i = 0; i < n1; i++)
```
```
        cin >> A[i];
```

    cout << "\nEnter the size of Second array:\n";

```
    cin >> n2;
```

    cout << "\nEnter the elements of Second array:\n";

```
    for (i = 0; i < n2; i++)
```
```
        cin >> B[i];
```
```
    // Sorting first array
```
```
    sort(A, A + n1);
```
```
    // Sorting second array 
```
```
    sort(B, B + n2);
```

    cout << "\nElements of First sorted array:\n";

```
    for (i = 0; i < n1; i++)
```
```
        cout << A[i] << " ";
```

    cout << "\nElements of Second sorted array:\n";

```
    for (i = 0; i < n2; i++) {
```
```
        cout << B[i] << " ";
```
```
    }
```
```
    ma.Merge(A, B, C, n1, n2);
```

    cout << "\nElements after Merging Arrays:\n";

```
    for (i = 0; i < (n1 + n2); i++) {
```
```
        cout << C[i] << " ";
```
```
    }
```
```
    return 0;
```
```
}
```

Program Explanation

1. Create a class merge_Array with Merge() function.
2. Get the input from the user for the size of the two arrays and the elements of the array also.
3. Create an object of class merge_Array i.e. ma.
4. Call sort() function to sort the two arrays.
5. Now display the two sorted array on the screen.
6. Call Merge() function through the object of class merge_Array.
7. For first while loop, traverse first array and second array simultaneously. Pick smaller of current elements in first array and second array, copy this smaller element to next position in the third array and move ahead in the third array and the array whose element is picked.
8. For second and third while loop, if there are remaining elements in the first array or second array, copy them also in the third array.
9. Return to the main function.
10. Print the final merged array in the main function.

Runtime Test Cases

Case 1 (Both the arrays have unsorted elements):
   Enter the size of First array:
   3
 
   Enter the elements of First array:
   3 6 1
 
   Enter the size of Second array:
   5
 
   Enter the elements of Second array:
   5 2 11 16 9
 
   Elements of First sorted array:
   1 3 6
   Elements of Second sorted array:
   2 5 9 11 16
   Elements after Merging Arrays:
   1 2 3 5 6 9 11 16
 
Case 2 (Both the arrays have sorted elements in ascending order):
   Enter the size of First array:
   4
 
   Enter the elements of First array:
   2 4 6 8
 
   Enter the size of Second array:
   6
 
   Enter the elements of Second array:
   1 3 5 7 9 11 
 
   Elements of First sorted array:
   2 4 6 8
   Elements of Second sorted array:
   1 3 5 7 9 11
   Elements after Merging Arrays:
   1 2 3 4 5 6 7 8 9 11
 
Case 3 (Both the arrays have sorted elements in descending order):
   Enter the size of First array:
   5
 
   Enter the elements of First array:
   9 6 5 3 1
 
   Enter the size of Second array:
   4
 
   Enter the elements of Second array:
   21 14 9 4
 
   Elements of First sorted array:
   1 3 5 6 9
   Elements of Second sorted array:
   4 9 14 21
   Elements after Merging Arrays:
   1 3 4 5 6 9 9 14 21

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Find Second Largest and Smallest Elements of an Array

» Next - C++ Program to Implement Variable Length Array

Next Steps: