Merge Two Sorted Arrays In C++ Program

Merging two sorted arrays into a single sorted array is a common task in programming, often encountered in algorithms like merge sort. This process efficiently combines ordered data structures while maintaining their sorted property.

In this article, you will learn how to merge two already sorted arrays in C++ using different approaches, including a manual two-pointer technique and leveraging the Standard Template Library (STL).

Problem Statement

Given two arrays, arr1 and arr2, both of which are already sorted in ascending order, the goal is to create a new array that contains all elements from arr1 and arr2, also sorted in ascending order. The combined array should maintain the sorted property without using a general sorting algorithm on the final collection.

This problem is crucial in scenarios where data arrives in pre-sorted chunks, and you need to consolidate it efficiently, such as merging results from parallel processing or combining datasets from different sorted sources.

Example

Consider two sorted arrays: arr1 = [1, 3, 5, 7] arr2 = [2, 4, 6, 8]

The merged sorted array should be: merged_arr = [1, 2, 3, 4, 5, 6, 7, 8]

Background & Knowledge Prerequisites

To understand the solutions presented, readers should have a basic understanding of:

• C++ Fundamentals: Variables, loops (for, while), conditional statements (if/else).
• Arrays: Declaring, initializing, and accessing elements in C++.
• Pointers (optional but helpful for std::merge context): Basic understanding of iterators or pointers to navigate arrays.
• Sorting Concepts: The idea that elements are arranged in a specific order (ascending in this case).

 

Relevant setup information: No specific external libraries are required beyond the standard C++ library. For the STL approach, and will be used.

Use Cases or Case Studies

Merging sorted arrays has various practical applications:

• Database Management: When combining query results from different indexes or partitions that are individually sorted.
• Data Analysis: Consolidating sorted data streams from sensors or financial feeds into a unified timeline.
• Algorithm Implementations: It is a core step in the Merge Sort algorithm, where smaller sorted subarrays are merged to form larger sorted arrays.
• File System Operations: Combining sorted lists of file names or directories from different locations.
• Resource Scheduling: Merging sorted lists of available time slots or resources to find optimal combinations.

 

Solution Approaches

Here are two effective methods to merge two sorted arrays:

1. Two-Pointer Approach (Manual Merge)

This classical approach uses three pointers: two for iterating through the input arrays and one for placing elements into the result array. It directly compares elements from both source arrays and selects the smaller one to place next.

• Summary: Iterates through both input arrays simultaneously using pointers, comparing elements and adding the smallest to a new array until all elements are merged.

 

// Merge Two Sorted Arrays (Two-Pointer)
#include <iostream>
#include <vector>
#include <algorithm> // Not strictly needed for this approach but good practice for vector ops

int main() {
    // Step 1: Define the two sorted input arrays
    std::vector<int> arr1 = {1, 3, 5, 7, 9};
    std::vector<int> arr2 = {2, 4, 6, 8, 10, 12};

    // Step 2: Calculate the size of the merged array and declare it
    int m = arr1.size();
    int n = arr2.size();
    std::vector<int> merged_arr(m + n);

    // Step 3: Initialize pointers for arr1, arr2, and merged_arr
    int i = 0; // Pointer for arr1
    int j = 0; // Pointer for arr2
    int k = 0; // Pointer for merged_arr

    // Step 4: Merge elements while both arrays have elements to compare
    while (i < m && j < n) {
        if (arr1[i] <= arr2[j]) {
            merged_arr[k] = arr1[i];
            i++;
        } else {
            merged_arr[k] = arr2[j];
            j++;
        }
        k++;
    }

    // Step 5: Add remaining elements from arr1 (if any)
    while (i < m) {
        merged_arr[k] = arr1[i];
        i++;
        k++;
    }

    // Step 6: Add remaining elements from arr2 (if any)
    while (j < n) {
        merged_arr[k] = arr2[j];
        j++;
        k++;
    }

    // Step 7: Print the merged array
    std::cout << "Merged array using Two-Pointer Approach: ";
    for (int val : merged_arr) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

• Sample Output:

Merged array using Two-Pointer Approach: 1 2 3 4 5 6 7 8 9 10 12

 

• Stepwise Explanation:

1. Initialize three integer pointers: i for arr1, j for arr2, and k for the merged_arr. All start at index 0.
2. Start a while loop that continues as long as both i is less than m (size of arr1) and j is less than n (size of arr2).
3. Inside the loop, compare arr1[i] and arr2[j].
   • If arr1[i] is less than or equal to arr2[j], place arr1[i] into merged_arr[k], then increment i and k.

• Otherwise (if arr2[j] is smaller), place arr2[j] into merged_arr[k], then increment j and k.

1. After the main loop finishes, one of the arrays might still have remaining elements. Add any leftover elements from arr1 to merged_arr using a separate while loop.
2. Similarly, add any leftover elements from arr2 to merged_arr using another while loop.
3. The merged_arr now contains all elements from arr1 and arr2 in sorted order.

2. Using std::merge from the C++ STL

The C++ Standard Template Library provides a convenient function std::merge in the header. This function efficiently merges two sorted ranges into a third sorted range.

• Summary: Leverages the std::merge algorithm to automatically combine elements from two sorted ranges (e.g., vectors) into a designated output range.

 

// Merge Two Sorted Arrays (STL std::merge)
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::merge

int main() {
    // Step 1: Define the two sorted input vectors
    std::vector<int> arr1 = {1, 3, 5, 7, 9};
    std::vector<int> arr2 = {2, 4, 6, 8, 10, 12};

    // Step 2: Create a destination vector with enough capacity
    // It should be large enough to hold all elements from both source vectors
    std::vector<int> merged_arr(arr1.size() + arr2.size());

    // Step 3: Use std::merge to combine the elements
    // Parameters:
    //   - arr1.begin(), arr1.end(): Input range 1
    //   - arr2.begin(), arr2.end(): Input range 2
    //   - merged_arr.begin(): Output iterator where the merged elements will be stored
    std::merge(arr1.begin(), arr1.end(),
               arr2.begin(), arr2.end(),
               merged_arr.begin());

    // Step 4: Print the merged array
    std::cout << "Merged array using std::merge: ";
    for (int val : merged_arr) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

• Sample Output:

Merged array using std::merge: 1 2 3 4 5 6 7 8 9 10 12

 

• Stepwise Explanation:

1. Include the header, which contains std::merge.
2. Define the two input std::vector objects, arr1 and arr2, ensuring they are already sorted.
3. Create a std::vector called merged_arr with a size equal to the sum of the sizes of arr1 and arr2. This vector will store the merged result.
4. Call std::merge:
   • The first two arguments (arr1.begin(), arr1.end()) specify the range of the first sorted array.

• The next two arguments (arr2.begin(), arr2.end()) specify the range of the second sorted array.
• The final argument (merged_arr.begin()) is an output iterator pointing to the beginning of the destination range where the merged elements will be placed.

1. std::merge efficiently combines the elements into merged_arr in sorted order.

Conclusion

Merging two sorted arrays is a fundamental operation with significant applications in various computing tasks. The two-pointer approach provides a clear, step-by-step understanding of the merging logic, making it excellent for educational purposes and situations where fine-grained control is needed. Conversely, std::merge offers a more concise, idiomatic C++ solution, leveraging the power and efficiency of the Standard Template Library. Both methods achieve the same goal of combining sorted data while preserving order.

Summary

• Merging sorted arrays involves combining two sorted lists into a single, larger sorted list.
• The Two-Pointer Approach manually iterates through both arrays, comparing elements and adding the smaller one to a new result array. It handles remaining elements after one array is exhausted.
• The std::merge function from the C++ STL ( header) provides an elegant and efficient way to achieve the same result with fewer lines of code. It takes two input ranges and an output iterator.
• Choosing between these approaches depends on whether you prefer explicit control over the merging logic or a more high-level, standard library solution.