Merge Two Sorted Arrays - C++ Program

This program teaches you how to merge two sorted arrays into a single sorted array in C++. Merging sorted arrays is a fundamental operation used in many algorithms, especially in merge sort and when combining sorted data from different sources. The result is a new array containing all elements from both arrays in sorted order.

1. What This Program Does

The program takes two sorted arrays and merges them into one sorted array. For example:

Array 1: [1, 3, 5, 7] (sorted)
Array 2: [2, 4, 6, 8] (sorted)
Merged: [1, 2, 3, 4, 5, 6, 7, 8] (sorted)

The key is that both input arrays are already sorted, which allows efficient merging by comparing elements from both arrays.

Example:

[1, 3, 5] + [2, 4, 6] → [1, 2, 3, 4, 5, 6]
[10, 20] + [15, 25, 30] → [10, 15, 20, 25, 30]

2. Header Files Used

#include <iostream>
- Provides cout and cin for input/output operations.
#include <algorithm>
- Provides merge() algorithm and other STL functions.
- Contains useful algorithms for array/container operations.

3. Declaring Variables

The program declares: int arr1[] = {1, 3, 5, 7}; int arr2[] = {2, 4, 6, 8}; int n1 = 4, n2 = 4;

arr1 is the first sorted array with 4 elements.
arr2 is the second sorted array with 4 elements.
n1 and n2 store the sizes of the arrays.

4. Creating the Merged Array

The program creates space for the merged result: int merged[n1 + n2];

The merged array needs space for all elements from both arrays.
Size = n1 + n2 = 4 + 4 = 8 elements.

5. The Two-Pointer Merge Algorithm

The core algorithm uses two pointers (indices):

int i = 0, j = 0, k = 0;

i points to current position in arr1.
j points to current position in arr2.
k points to current position in merged array.

Main Merge Loop:

while (i < n1 && j < n2) { if (arr1[i] < arr2[j]) { merged[k++] = arr1[i++]; } else { merged[k++] = arr2[j++]; } }

How it works step-by-step (for [1,3,5,7] and [2,4,6,8]):

Initial: i=0, j=0, k=0

Compare arr1[0]=1 with arr2[0]=2
1 < 2, so merged[0]=1, i=1, k=1
Merged: [1, ...]

Step 1: i=1, j=0, k=1

Compare arr1[1]=3 with arr2[0]=2
3 > 2, so merged[1]=2, j=1, k=2
Merged: [1, 2, ...]

Step 2: i=1, j=1, k=2

Compare arr1[1]=3 with arr2[1]=4
3 < 4, so merged[2]=3, i=2, k=3
Merged: [1, 2, 3, ...]

Step 3: i=2, j=1, k=3

Compare arr1[2]=5 with arr2[1]=4
5 > 4, so merged[3]=4, j=2, k=4
Merged: [1, 2, 3, 4, ...]

Step 4: i=2, j=2, k=4

Compare arr1[2]=5 with arr2[2]=6
5 < 6, so merged[4]=5, i=3, k=5
Merged: [1, 2, 3, 4, 5, ...]

Step 5: i=3, j=2, k=5

Compare arr1[3]=7 with arr2[2]=6
7 > 6, so merged[5]=6, j=3, k=6
Merged: [1, 2, 3, 4, 5, 6, ...]

Step 6: i=3, j=3, k=6

Compare arr1[3]=7 with arr2[3]=8
7 < 8, so merged[6]=7, i=4, k=7
Merged: [1, 2, 3, 4, 5, 6, 7, ...]

Loop ends (i >= n1), now copy remaining from arr2.

6. Copying Remaining Elements

After the main loop, one array may have remaining elements:

while (i < n1) merged[k++] = arr1[i++]; while (j < n2) merged[k++] = arr2[j++];

Why needed?

The main loop stops when one array is exhausted.
The other array may still have elements.
These remaining elements are already sorted, so just copy them.

In our example:

After main loop: i=4 (arr1 exhausted), j=3, k=7
arr2 still has arr2[3]=8
Copy: merged[7]=8, j=4, k=8
Final: [1, 2, 3, 4, 5, 6, 7, 8]

7. Other Methods (Mentioned but not shown in code)

Method 2: Using merge() Algorithm

#include <algorithm> int merged[n1 + n2]; merge(arr1, arr1 + n1, arr2, arr2 + n2, merged);

STL merge() function does the merging automatically.
Parameters: start1, end1, start2, end2, output
Simplest method - one line of code.

Method 3: Using Vectors

vector<int> vec1(arr1, arr1 + n1); vector<int> vec2(arr2, arr2 + n2); vector<int> merged; merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(merged));

Works with vectors instead of arrays.
More flexible and dynamic.

Method 4: Using Priority Queue

priority_queue<int, vector<int>, greater<int>> pq; // Add all elements, then extract // Less efficient but demonstrates priority queue usage

Method 5: Using Recursion

vector<int> mergeRecursive(vector<int>& arr1, vector<int>& arr2) { // Recursive merge implementation // Base case: one array empty // Recursive case: compare and merge }

Recursive approach - more complex but educational.

8. Displaying the Result

The program prints: cout << "Merged array: "; for (int i = 0; i < n1 + n2; i++) { cout << merged[i] << " "; }

Output: Merged array: 1 2 3 4 5 6 7 8

The merged array contains all elements in sorted order.

9. Understanding the Algorithm

Key Insight: Since both arrays are sorted, we can merge efficiently by:

Comparing the smallest remaining elements from both arrays.
Taking the smaller one and moving to the next element in that array.
Repeating until one array is exhausted.
Copying remaining elements from the other array.

Why it works:

Both arrays are sorted, so the smallest unprocessed element in each array is at the current pointer.
By always taking the smaller of the two, we maintain sorted order.
This is the core idea behind merge sort algorithm.

10. Time and Space Complexity

Time Complexity: O(n1 + n2)

We process each element exactly once.
Linear time - very efficient.

Space Complexity: O(n1 + n2)

Need space for the merged array.
Can be done in-place for some cases, but typically needs extra space.

11. When to Use Each Method

Two Pointers: Best for learning - shows the algorithm clearly.
merge() Algorithm: Best for most cases - simple, optimized, recommended.
Vectors: When working with dynamic data or need vector features.
Priority Queue: Less efficient - mainly for educational purposes.
Recursion: Educational - helps understand recursive thinking.

Best Practice: Use merge() for most applications - it's simple, efficient, and optimized.

12. Common Use Cases

Merge Sort:

Core operation in merge sort algorithm.
Divides array, sorts halves, then merges.

Combining Sorted Data:

Merging sorted lists from different sources.
Database operations (merge join).
Combining sorted search results.

Interview Questions:

Common coding interview problem.
Tests understanding of two-pointer technique.
Foundation for more complex problems.

13. Important Considerations

Both Arrays Must Be Sorted:

This algorithm only works if both input arrays are sorted.
If not sorted, result will not be sorted.
Sort arrays first if needed.

Equal Elements:

When arr1[i] == arr2[j], either can be taken first.
The algorithm takes from arr2 (else branch).
Order of equal elements is preserved within each array.

Different Array Sizes:

Algorithm works with arrays of different sizes.
Remaining elements from larger array are copied at the end.

14. return 0;

This ends the program successfully.

Summary

Merging two sorted arrays combines them into one sorted array.
Two-pointer technique efficiently compares and merges elements.
Always compare smallest remaining elements from both arrays.
Copy remaining elements after one array is exhausted.
Time complexity is O(n1 + n2) - linear and efficient.
merge() algorithm is the simplest and most recommended method.
Understanding merge is essential for merge sort and combining sorted data.

This program is fundamental for beginners learning array algorithms, understanding the two-pointer technique, and preparing for more advanced algorithms like merge sort in C++ programs.

Output