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.