Merge Two Sorted Arrays
Merge Two Sorted Arrays in C++ (5 Examples)
C++ Merge Two Sorted Arrays Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 8};
int n1 = 4, n2 = 4;
int merged[n1 + n2];
int i = 0, j = 0, k = 0;
// Merge while both arrays have elements
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
merged[k++] = arr1[i++];
} else {
merged[k++] = arr2[j++];
}
}
// Copy remaining elements
while (i < n1) merged[k++] = arr1[i++];
while (j < n2) merged[k++] = arr2[j++];
cout << "Merged array: ";
for (int i = 0; i < n1 + n2; i++) {
cout << merged[i] << " ";
}
cout << endl;
return 0;
}Merged array: 1 2 3 4 5 6 7 8
Understanding Merge Two Sorted Arrays
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:
The key is that both input arrays are already sorted, which allows efficient merging by comparing elements from both arrays.
Example:
---
2. Header Files Used
---
3. Declaring Variables
The program declares:
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 8};
int n1 = 4, n2 = 4;
---
4. Creating the Merged Array
The program creates space for the merged result:
int merged[n1 + n2];
---
5. The Two-Pointer Merge Algorithm
The core algorithm uses two pointers (indices):
int i = 0, j = 0, k = 0;
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]):
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?
In our example:
---
7. Other Methods (Mentioned but not shown in code)
Method 2: Using merge() Algorithm
int merged[n1 + n2];
merge(arr1, arr1 + n1, arr2, arr2 + n2, merged);
#include <algorithm>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));
Method 4: Using Priority Queue
priority_queue<int, vector<int>, greater<int>> pq;
// Add all elements, then extract
// Less efficient but demonstrates priority queue usageMethod 5: Using Recursion
vector<int> mergeRecursive(vector<int>& arr1, vector<int>& arr2) {
}
---
// Recursive merge implementation
// Base case: one array empty
// Recursive case: compare and merge8. Displaying the Result
The program prints:
for (int i = 0; i < n1 + n2; i++) {
cout << merged[i] << " ";
}
Output:
The merged array contains all elements in sorted order.
---
cout << "Merged array: ";9. Understanding the Algorithm
Key Insight
: Since both arrays are sorted, we can merge efficiently by:
Why it works
:
---
10. Time and Space Complexity
Time Complexity
: O(n1 + n2)
Space Complexity
: O(n1 + n2)
---
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
:
Combining Sorted Data
:
Interview Questions
:
---
13. Important Considerations
Both Arrays Must Be Sorted
:
Equal Elements
:
Different Array Sizes
:
---
14. return 0;
This ends the program successfully.
---
Summary
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.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for Merge Two Sorted Arrays
This C++ program is part of the "Array Operations Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.