Merging two sorted arrays into a single sorted array is a common task in various applications, particularly in the field of data processing and algorithms. This article will guide you through the implementation of a C++ program to merge two sorted arrays, providing multiple examples to demonstrate various solutions and their outputs.
Prerequisites
Before diving into the implementation, you should have:
- Basic understanding of C++ programming.
- Familiarity with arrays and basic sorting algorithms.
With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.
1. Merging Two Sorted Arrays In C++
1.1 Simple Merging Approach
Let’s start with a straightforward approach to merge two sorted arrays into a single sorted array.
#include <iostream>
#include <vector>
std::vector<int> mergeSortedArrays(const std::vector<int>& arr1, const std::vector<int>& arr2) {
int n1 = arr1.size();
int n2 = arr2.size();
std::vector<int> mergedArray(n1 + n2);
int i = 0, j = 0, k = 0;
// Merge the arrays while there are elements in both
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
mergedArray[k++] = arr1[i++];
} else {
mergedArray[k++] = arr2[j++];
}
}
// Copy remaining elements of arr1, if any
while (i < n1) {
mergedArray[k++] = arr1[i++];
}
// Copy remaining elements of arr2, if any
while (j < n2) {
mergedArray[k++] = arr2[j++];
}
return mergedArray;
}
int main() {
std::vector<int> arr1 = {1, 3, 5, 7};
std::vector<int> arr2 = {2, 4, 6, 8};
std::vector<int> mergedArray = mergeSortedArrays(arr1, arr2);
std::cout << "Merged array: ";
for (int val : mergedArray) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
1.2 Output Explanation
In this example, the input arrays are {1, 3, 5, 7} and {2, 4, 6, 8}. The program merges them into a single sorted array.
Merged array: 1 2 3 4 5 6 7 8
1.3 Time Complexity
The time complexity of this approach is O(n1+n2)O(n1 + n2)O(n1+n2) where n1n1n1 and n2n2n2 are the sizes of the two arrays. This is because we traverse each array once.
2. Handling Edge Cases
2.1 One Empty Array
Let’s handle the edge case where one of the arrays is empty.
int main() {
std::vector<int> arr1 = {};
std::vector<int> arr2 = {2, 4, 6, 8};
std::vector<int> mergedArray = mergeSortedArrays(arr1, arr2);
std::cout << "Merged array: ";
for (int val : mergedArray) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
2.2 Output Explanation
In this example, the input arrays are {} and {2, 4, 6, 8}. The program merges them into a single sorted array.
Merged array: 2 4 6 8
2.3 Both Arrays Empty
Now let’s handle the case where both arrays are empty.
int main() {
std::vector<int> arr1 = {};
std::vector<int> arr2 = {};
std::vector<int> mergedArray = mergeSortedArrays(arr1, arr2);
std::cout << "Merged array: ";
for (int val : mergedArray) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
2.4 Output Explanation
In this example, the input arrays are both empty {} and {}. The program merges them into a single sorted array.
Merged array:
This ensures that the program handles edge cases gracefully without crashing.
3. Using C++ Standard Library Functions
3.1 Using std::merge
We can also utilize the C++ Standard Library function std::merge from the <algorithm> header to simplify the process.
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> mergeSortedArrays(const std::vector<int>& arr1, const std::vector<int>& arr2) {
std::vector<int> mergedArray(arr1.size() + arr2.size());
std::merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), mergedArray.begin());
return mergedArray;
}
int main() {
std::vector<int> arr1 = {1, 3, 5, 7};
std::vector<int> arr2 = {2, 4, 6, 8};
std::vector<int> mergedArray = mergeSortedArrays(arr1, arr2);
std::cout << "Merged array: ";
for (int val : mergedArray) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
3.2 Output Explanation
In this example, the input arrays are {1, 3, 5, 7} and {2, 4, 6, 8}. The program uses std::merge to combine them into a single sorted array.
Merged array: 1 2 3 4 5 6 7 8
Conclusion
A C++ program to merge two sorted arrays can be implemented using different approaches. The simple approach involves manually merging the arrays, while the more efficient approach utilizes the std::merge function from the C++ Standard Library.