Home » Data Structure » Array Data Structure

Merge an array of size n into another array of size m+n

C++ implementation to merge an array of size n into another array of size m+n.
Submitted by Vikneshwar GK, on January 22, 2022

Consider two sorted arrays of the sizes m+n and n, respectively. The first array, which is of size m+n, has only m elements; therefore n positions are empty. In the second array, which is of size n, all positions are filled. The task at hand is to merge the second array into the first array such that the merged array is overall sorted.

Example:

Note: For implementation purposes, we will use -1 as the unfilled position in the array.

Input:
test1[] = {2, -1, 3, -1, -1, 9, -1, 12, -1, 20}
test2[] = {4, 5, 11, 13, 25}

Output:
test1[] = {2, 3, 4, 5, 9, 11, 12, 13, 20, 25}

Input:
test1[] = {1, -1, 5, 8, -1, -1, 10, -1}
test2[] = {2, 4, 7, 9}

Output:
test1[] = {1, 2, 4, 5, 7, 8, 9, 10}

Solution:

Since both arrays are already in sorted format, we can directly start comparing and merging them. But before that, we need to move all the elements in the m+n size array to the end. Then we can merge the arrays. Totally, it involves the following steps:

• Step 1: Move all the elements in the m+n array to the end.
• Step 2: Set 3 pointers, pointer 1 representing the end of m+n array, pointer 2 representing the start of n array, and pointer 3 representing the start of m+n array.
• Step 3: Compare pointer 1 and pointer 2 and place the minimum value in pointer 3.

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

// Function to move m+n array
// elements to the end
void pushElements(int MN[], int length)
{
    int j = length - 1;
    for (int i = length - 1; i >= 0; i--)
        if (MN[i] != -1) {
            MN[j] = MN[i];
            j--;
        }
}

// Function to merge two array
void mergeArray(int MN[], int N[], int mnLength, int nLength)
{
    // initialize the pointers
    int i = nLength;
    int j = 0;
    int k = 0;

    while (i < mnLength && j < nLength) {

        // if m+n array element is lesser than 
        // n array element
        if (MN[i] <= N[j]) {
            MN[k] = MN[i];
            k++;
            i++;
        }
        else {
            MN[k] = N[j];
            k++;
            j++;
        }
    }

    while (i < mnLength) {
        MN[k] = MN[i];
        k++;
        i++;
    }

    while (j < nLength) {
        MN[k] = N[j];
        k++;
        j++;
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
}

// main function
int main()
{
    int array1[100], array2[100], length1, length2;
    
    cout << "Enter Number of elements for array 1: ";
    cin >> length1;

    cout << "Note: Enter -1 for the unfilled positions" << endl;
    for (int i = 0; i < length1; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array1[i];
    }

    cout << "Enter Number of elements for array 2: ";
    cin >> length2;

    for (int j = 0; j < length2; j++) {
        cout << "Enter element " << j + 1 << ":";
        cin >> array2[j];
    }

    pushElements(array1, length1);

    mergeArray(array1, array2, length1, length2);

    printArray(array1, length1);
    
    return 0;
}

Output:

Enter Number of elements for array 1: 10
Note: Enter -1 for the unfilled positions
Enter element 1:2
Enter element 2:-1
Enter element 3:3
Enter element 4:-1
Enter element 5:-1
Enter element 6:9
Enter element 7:-1
Enter element 8:12
Enter element 9:-1
Enter element 10:20
Enter Number of elements for array 2: 5
Enter element 1:4
Enter element 2:5
Enter element 3:11
Enter element 4:13
Enter element 5:25
2 3 4 5 9 11 12 13 20 25 

Time Complexity: O(m+n)