Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Sorting the combined array works but ignores that both halves are already sorted.
  2. 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