1. Идея

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

Главная идея — не сортировать всё заново, а воспользоваться тем, что оба списка уже упорядочены. Для этого удобно идти по ним двумя указателями:

• i — текущая позиция в массиве a
• j — текущая позиция в массиве b

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

• если a[i] <= b[j], добавляем a[i] в ответ и двигаем i
• иначе добавляем b[j] и двигаем j

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

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

1. Если оба массива отсортированы, то минимальный из оставшихся элементов всегда стоит либо в a[i], либо в b[j].

2. После того как мы выбрали меньший элемент, он точно должен идти следующим в итоговом ответе.

3. Если элементы равны, можно брать элемент из первого массива раньше второго. Порядок останется неубывающим:

   • например, при a[i] = 5 и b[j] = 5 можно сначала добавить 5 из a, потом 5 из b.

4. Когда один из массивов закончился, оставшаяся часть другого массива уже отсортирована, значит её можно просто дописать в ответ без дополнительных проверок.

5. Такой подход работает за линейное время, потому что каждый указатель движется только вперёд и каждый элемент рассматривается ровно один раз.

3. Алгоритм

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

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

Докажем, что алгоритм действительно строит правильное отсортированное слияние.

Пусть в некоторый момент указатели стоят на позициях i и j. Это значит:

• элементы a[0..i-1] уже обработаны
• элементы b[0..j-1] уже обработаны
• в ответ уже записаны все нужные элементы из этих частей, причём в правильном порядке

Теперь нужно выбрать следующий элемент ответа.

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

• минимальный элемент из a — это a[i]
• минимальный элемент из b — это b[j]

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

• если a[i] <= b[j], следующим в ответе должен идти a[i]
• иначе следующим должен идти b[j]

Именно это и делает алгоритм.

После каждого шага мы добавляем правильный следующий элемент, поэтому инвариант сохраняется: ответ остаётся корректным префиксом итогового слияния.

Когда один из массивов закончился, все элементы другого массива уже идут в неубывающем порядке и не меньше уже записанных элементов, поэтому их можно просто дописать.

Следовательно, после завершения алгоритма в res будет записано ровно n + m элементов, и это будет правильное отсортированное слияние двух массивов.

5. Сложность

Пусть размеры массивов равны n и m.

• Время работы: 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 j = 0; j < m; j++) {
        cin >> b[j];
    }

    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)