Challenge: Merge Two Sorted Lists

Lab C++ Intermediate 20 points

Read two sorted lists and merge them into one sorted list using two pointers (don't just join them and sort).

Input

Line 1: n, then n sorted numbers. Line 2: m, then m sorted numbers.

Output

The merged sorted list, separated by spaces.

Example

Input

3 1 4 7
4 2 3 8 9

Output

1 2 3 4 7 8 9

Sample input available Sample output available

Editor

C++

Hints

Compare a[i] and b[j]; take the smaller and move that pointer.

Copy whatever is left over at the end.

Solution explanation

Every number is taken once: O(n + m). This is the heart of merge sort (Module 8).

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    cin >> m;
    vector<int> b(m);
    for (int& x : b) cin >> x;
    vector<int> out;
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) out.push_back(a[i++]);
        else out.push_back(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;
}

Output

Answer