1. Идея

Даны два массива, каждый уже отсортирован по неубыванию. Нужно получить один общий отсортированный массив.

Самая естественная идея — не сортировать всё заново, а идти по обоим журналам одновременно двумя указателями:

• i — текущая позиция в первом журнале,
• j — текущая позиция во втором журнале.

На каждом шаге сравниваем a[i] и b[j]:

• если a[i] <= b[j], берём элемент из первого журнала;
• иначе берём элемент из второго.

Так мы всегда добавляем в ответ наименьший из ещё не использованных элементов.

2. Наблюдения

1. Оба журнала уже отсортированы, а значит минимальный неиспользованный элемент в каждом журнале всегда стоит на текущем указателе.

2. Чтобы выбрать следующий элемент ответа, достаточно сравнить только a[i] и b[j]. Смотреть дальше не нужно.

3. Когда один журнал закончился, все элементы второго уже можно просто дописать в конец ответа:

   • они уже отсортированы внутри себя;
   • они не меньше тех элементов, которые уже были добавлены раньше.

4. Ограничения до 2 * 10^5 подсказывают, что решение должно работать примерно за линейное время. Полная пересортировка тоже могла бы пройти, но здесь есть более прямой и правильный по смыслу способ — классическое слияние двух отсортированных массивов.

3. Алгоритм

Пусть:

• a — первый журнал длины n,
• b — второй журнал длины m.

Делаем так:

1. Считываем оба массива.
2. Создаём пустой массив res для ответа.
3. Заводим два указателя: i = 0, j = 0.
4. Пока i < n и j < m:
   • если a[i] <= b[j], добавляем a[i] в res и увеличиваем i;
   • иначе добавляем b[j] в res и увеличиваем j.
5. Если в первом массиве ещё остались элементы, дописываем их в res.
6. Если во втором массиве ещё остались элементы, дописываем их в res.
7. Выводим res.

4. Почему это работает

Докажем, что алгоритм действительно строит объединённый массив в неубывающем порядке.

В каждый момент времени:

• элементы a[0..i-1] и b[0..j-1] уже использованы,
• элементы a[i..] и b[j..] ещё не использованы.

Так как оба массива отсортированы, среди всех неиспользованных элементов:

• минимальный элемент первого массива — это a[i],
• минимальный элемент второго массива — это b[j].

Значит, минимальный элемент среди вообще всех оставшихся — это минимум из a[i] и b[j].

Именно его алгоритм и добавляет следующим в ответ. Поэтому следующий элемент выбирается правильно.

После этого один из указателей сдвигается, и рассуждение повторяется для оставшейся части.

Когда один массив закончился, во втором остаются элементы, которые:

• уже отсортированы,
• не меньше последнего добавленного корректного элемента.

Значит, их можно просто дописать в конец без нарушения порядка.

Итак, алгоритм:

• использует все элементы обоих массивов ровно по одному разу;
• сохраняет неубывающий порядок.

Следовательно, ответ корректен.

5. Сложность

Каждый элемент обоих массивов рассматривается и добавляется в ответ ровно один раз.

• Время: O(n + m)
• Память: O(n + m) на массив ответа

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<long long> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    vector<long long> res;
    res.reserve(n + m);

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) {
            res.push_back(a[i]);
            i++;
        } else {
            res.push_back(b[j]);
            j++;
        }
    }

    while (i < n) {
        res.push_back(a[i]);
        i++;
    }

    while (j < m) {
        res.push_back(b[j]);
        j++;
    }

    for (int k = 0; k < (int)res.size(); k++) {
        if (k > 0) {
            cout << ' ';
        }
        cout << res[k];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

i = 0
j = 0
res = []

while i < n and j < m:
    if a[i] <= b[j]:
        res.append(a[i])
        i += 1
    else:
        res.append(b[j])
        j += 1

while i < n:
    res.append(a[i])
    i += 1

while j < m:
    res.append(b[j])
    j += 1

print(*res)