Sorted Merge Arrays - C++ Solution

1. Introduction

In this blog post, we will discuss a fundamental problem in array manipulation and sorting algorithms - merging two sorted arrays. This is a common scenario in data processing where we need to combine data from two sorted sources into a single, sorted sequence.

Problem

Given two integer arrays, both sorted in increasing order, the challenge is to merge these arrays into a single array, which is also sorted in increasing order.

2. Solution Steps

1. Initialize three indices - one for each of the two arrays and one for the merged array.

2. Compare elements of the two arrays and insert the smaller one into the merged array, incrementing the respective index.

3. If one array is exhausted, append the remaining elements of the other array to the merged array.

4. Continue this process until all elements are merged into a single sorted array.

3. Code Program

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

// Function to merge two sorted arrays
vector<int> mergeSortedArrays(const vector<int>& X, const vector<int>& Y) {
    size_t i = 0, j = 0; // Indices for X and Y arrays
    vector<int> merged; // Array to store merged elements

    while (i < X.size() && j < Y.size()) {
        // Compare elements of X and Y, and add the smaller one to 'merged'
        if (X[i] < Y[j]) {
            merged.push_back(X[i]);
            i++; // Increment index of X
        } else {
            merged.push_back(Y[j]);
            j++; // Increment index of Y
        }
    }

    // Add remaining elements of X to 'merged' if any
    while (i < X.size()) {
        merged.push_back(X[i]);
        i++;
    }

    // Add remaining elements of Y to 'merged' if any
    while (j < Y.size()) {
        merged.push_back(Y[j]);
        j++;
    }

    return merged;
}

int main() {
    vector<int> X = {1, 3, 5, 7};
    vector<int> Y = {2, 4, 6};
    vector<int> result = mergeSortedArrays(X, Y);

    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

1 2 3 4 5 6 7

Explanation:

The function mergeSortedArrays takes two sorted arrays X and Y as inputs. It uses two pointers to iterate through both arrays, comparing elements and adding the smaller of the two to the merged array. Once all elements from one array are added, the remaining elements of the other array are appended. The output [1, 2, 3, 4, 5, 6, 7] is the merged sorted array from the given inputs X = [1, 3, 5, 7] and Y = [2, 4, 6].