Practice › Arrays
Merge Two Sorted Arrays
Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Merge two arrays that are each sorted in non-decreasing order into one sorted array.
Input
Line 1: n. Line 2: n integers. Line 3: m. Line 4: m integers.
Output
The merged array, space-separated.
Constraints
- 1 ≤ n, m ≤ 10^5
Use two pointers — O(n + m), no sorting needed.
Example 1
Input
3 1 3 5 3 2 4 6
Output
1 2 3 4 5 6
Example 2
Input
2 1 1 1 1
Output
1 1 1
Hints
- Sorting the combined array works but ignores that both halves are already sorted.
- Use two pointers and always take the smaller front element.
Approach
Pointer i walks the first array and j the second. Append the smaller of a[i] and b[j] and advance that pointer. When one array runs out, append the rest of the other.
Complexity: O(n + m) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
cin >> m;
vector<long long> b(m);
for (auto &x : b) cin >> x;
vector<long long> out;
int i = 0, j = 0;
while (i < n && j < m) out.push_back(a[i] <= b[j] ? a[i++] : b[j++]);
while (i < n) out.push_back(a[i++]);
while (j < m) out.push_back(b[j++]);
for (size_t k = 0; k < out.size(); k++) cout << out[k] << (k + 1 < out.size() ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a = data[1 : n + 1]
m = data[n + 1]
b = data[n + 2 : n + 2 + m]
out, i, j = [], 0, 0
while i < n and j < m:
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1
out.extend(a[i:])
out.extend(b[j:])
print(*out)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int m = sc.nextInt();
long[] b = new long[m];
for (int i = 0; i < m; i++) b[i] = sc.nextLong();
StringBuilder sb = new StringBuilder();
int i = 0, j = 0;
while (i < n || j < m) {
long v = (j >= m || (i < n && a[i] <= b[j])) ? a[i++] : b[j++];
if (sb.length() > 0) sb.append(' ');
sb.append(v);
}
System.out.println(sb);
}
}Solve Merge Two Sorted Arrays online · All practice problems