Merge Sorted Array
221 Views
You are given two integer arrays arr1 and arr2 sorted in accending order and two integers m and n representing the number of elements in arr1 and arr2 respectively. size of arr1 is m+n.
Merge arr1 and arr2 into a single array (arr1) sorted in accending order.
Example 1
Input : arr1 = [4, 8, 13, 25, 0, 0], m = 4, arr2 = [2, 23], n = 2
Output : [2, 4, 8, 13, 23, 25]
Constraints : -
arr1.length == m + n arr2.length == n 1 <= m + n <= 200 0 <= m, n <= 200 -109 <= arr1[i], arr2[j] <= 109
Brute Force Approach
- Copy all elements of arr2 into the unused space of arr1.
- Sort the entire arr1 array.
C++
Java
C#
Python
#include <iostream>
#include <vector>
#include <algorithm>
void merge(std::vector<int>& arr1, int m, const std::vector<int>& arr2, int n) {
for (int i = 0; i < n; ++i) {
arr1[m + i] = arr2[i];
}
std::sort(arr1.begin(), arr1.end());
}
int main() {
std::vector<int> arr1 = {1, 3, 5, 0, 0, 0}; // extra space for arr2
std::vector<int> arr2 = {2, 4, 6};
int m = 3;
int n = 3;
merge(arr1, m, arr2, n);
std::cout << "Merged array: ";
for (int num : arr1) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}Merged array: [1, 2, 3, 4, 5, 6]
⏱️ Time Complexity : O((m + n) log(m + n))
🧪 Space Complexity : O(1)
Merge Using Extra Space
- Use a new array and merge like in merge sort
- Compare elements from both arrays and place the smaller one in the result
- Finally, copy merged array back to arr1
C++
Java
C#
Python
#include <iostream>
#include <vector>
#include <algorithm>
void merge(std::vector<int>& arr1, int m, const std::vector<int>& arr2, int n) {
std::vector<int> merged(m + n);
int i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (arr1[i] <= arr2[j]) {
merged[k++] = arr1[i++];
} else {
merged[k++] = arr2[j++];
}
}
while (i < m) merged[k++] = arr1[i++];
while (j < n) merged[k++] = arr2[j++];
for (int l = 0; l < m + n; l++) {
arr1[l] = merged[l];
}
}
int main() {
std::vector<int> arr1 = {1, 3, 5, 0, 0, 0}; // size = m + n
std::vector<int> arr2 = {2, 4, 6};
int m = 3, n = 3;
merge(arr1, m, arr2, n);
std::cout << "Merged Array: ";
for (int num : arr1) std::cout << num << " ";
std::cout << std::endl;
return 0;
}Merged Array: [1, 2, 3, 4, 5, 6]
⏱️ Time Complexity : O(m + n)
🧪 Space Complexity : O(m + n)
🚀 Optimal In-Place Approach: Two-Pointer from the End
- Work backwards from the end of arr1.
- Start comparing from m-1 and n-1 and place the largest element at m+n-1 position.
- Avoids extra space and works in-place
C++
Java
C#
Python
Java Script
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr1, int m, const std::vector<int>& arr2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (i >= 0 && j >= 0) {
if (arr1[i] > arr2[j]) {
arr1[k--] = arr1[i--];
} else {
arr1[k--] = arr2[j--];
}
}
while (j >= 0) {
arr1[k--] = arr2[j--];
}
}
int main() {
std::vector<int> arr1 = {1, 3, 5, 0, 0, 0};
std::vector<int> arr2 = {2, 4, 6};
int m = 3;
int n = 3;
merge(arr1, m, arr2, n);
std::cout << "Merged Array: ";
for (int num : arr1) std::cout << num << " ";
std::cout << std::endl;
return 0;
}Merged Array: [1, 2, 3, 4, 5, 6]
⏱️ Time Complexity : O(m + n)
🧪 Space Complexity : O(1)
Complexity Table
| Approach | Time Complexity | Space Complexity | Key Idea | Notes |
|---|---|---|---|---|
| Brute Force | O((m+n) log(m+n)) | O(1) | Copy and sort | Simple but inefficient |
| Extra Space Merge | O(m + n) | O(m + n) | Merge into a third array | Better but uses space |
| In-Place Optimal | O(m + n) | O(1) | Merge from the back using two-pointers | Best approach |