# 1. Introduction

"Merging Arrays II" is an interesting variant of array merging problems. It involves merging two sorted arrays when one array, X[], has vacant cells (represented by 0s) and is large enough to hold all elements from the second array, Y[]. The challenge lies in merging them into X[] while maintaining sorted order and utilizing vacant cells.

## Problem

Given two sorted integer arrays X[] and Y[], where X[] has a size m (including n vacant cells represented by 0s) and Y[] has a size n, merge Y[] into X[] in a sorted manner. The resulting array X[] should contain all elements from both arrays, sorted in ascending order.

# 2. Solution Steps

1. Move all non-zero elements of X[] to the end of the array.

2. Use two pointers: one for the non-zero elements of X[] and one for Y[].

3. Compare elements from the end of the non-zero section of X[] and from Y[].

4. Place the larger element at the end of X[] and move the pointers accordingly.

5. Continue this process until all elements from Y[] are merged into X[].

# 3. Code Program

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

// Function to merge Y[] into X[]
void merge(int X[], int Y[], int m, int n) {
// Move non-zero elements of X[] to the end
int k = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (X[i] != 0) {
X[k--] = X[i];
}
}

// Merge elements of Y[] and X[]
int i = n; // Index of the non-zero start of X[]
int j = 0; // Index of Y[]
k = 0; // Index for the resultant X[]

// Merge until Y[] is exhausted
while (j < n) {
if (i < m && X[i] <= Y[j]) {
X[k++] = X[i++];
} else {
X[k++] = Y[j++];
}
}
}

int main() {
int X[] = {0, 2, 0, 3, 0, 5, 6, 0, 0};
int Y[] = {1, 8, 9, 10, 15};
int m = sizeof(X) / sizeof(X[0]);
int n = sizeof(Y) / sizeof(Y[0]);

merge(X, Y, m, n);

// Print merged array
for (int i = 0; i < m; i++) {
cout << X[i] << " ";
}
cout << endl;

return 0;
}
``````

### Output:

1 2 3 5 6 8 9 10 15

### Explanation:

The program starts by moving all non-zero elements of X[] to its end. This creates space at the beginning of X[] to merge elements from Y[]

Using two pointers, it compares elements from Y[] and the non-zero section of X[], placing the smaller of the two elements into the correct position in X[]

This process continues until all elements of Y[] are merged into X[], resulting in a sorted merged array.

The approach efficiently utilizes the available space in X[] and merges the arrays in place.