Merge Arrays - C++ Solution

1. Introduction

The "Merge Arrays" problem is a fundamental exercise in array manipulation, particularly focusing on the concept of merging while maintaining sorted order. This problem is a variant of the classical merge step in the merge sort algorithm but requires in-place merging without extra space.

Problem

Given two sorted integer arrays X[] of size m and Y[] of size n, the task is to merge these arrays. The merged arrays should maintain sorted order, with X[] containing the first m smallest elements and Y[] containing the remaining elements.

2. Solution Steps

1. Start from the last element of Y[] and the first element of X[].

2. Compare each element of Y[] with the first element of X[].

3. If an element of Y[] is smaller, swap it with the first element of X[].

4. After each swap, sort X[].

5. Continue this process until all elements of Y[] have been compared.

3. Code Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Utility function to merge arrays X[] and Y[]
void mergeArrays(vector<int>& X, vector<int>& Y) {
    int m = X.size(), n = Y.size();

    // Compare each element of Y[] with the first element of X[]
    for (int i = 0; i < n; i++) {
        // If the element of Y[] is smaller than the first element of X[]
        if (Y[i] < X[0]) {
            // Swap it with the first element of X[]
            swap(Y[i], X[0]);

            // Sort X[] so that the next smallest element comes to the first position
            int first = X[0];
            int k;
            for (k = 1; k < m && X[k] < first; k++) {
                X[k - 1] = X[k];
            }
            X[k - 1] = first;
        }
    }
}

int main() {
    vector<int> X = {1, 4, 7, 8, 10};
    vector<int> Y = {2, 3, 9};

    mergeArrays(X, Y);

    // Print the merged arrays
    cout << "X[] = ";
    for (int x : X) {
        cout << x << " ";
    }
    cout << "\nY[] = ";
    for (int y : Y) {
        cout << y << " ";
    }
    cout << endl;

    return 0;
}

Output:

X[] = 1 2 3 4 7

Explanation:

The function mergeArrays performs an in-place merge of the two arrays. 

It begins by comparing elements of Y[] with the first element of X[]. If any element of Y[] is smaller, it is swapped with the first element of X[]

After each swap, X[] is sorted to ensure it always contains the smallest elements in order. 

This approach guarantees the sorted order of both arrays while merging them without additional space, showcasing efficient array manipulation.


Comments