Объединение двух отсортированных векторов в один

Условие

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

std::vector<int> mergeArrays(std::vector<int> sorted1, std::vector<int> sorted2) {
    // объединить два отсортированных массива
}

Ответ

Сливайте два диапазона алгоритмом std::merge в отдельный вектор. Он сохраняет все элементы, включая повторяющиеся, и требует, чтобы оба входа уже были отсортированы.

#include <algorithm>
#include <iterator>
#include <vector>

std::vector<int> mergeArrays(const std::vector<int>& first,
                             const std::vector<int>& second) {
    std::vector<int> merged;
    std::merge(first.begin(), first.end(),
               second.begin(), second.end(), std::back_inserter(merged));
    return merged;
}

Константные ссылки избегают копирования аргументов; при необходимости исходную сигнатуру можно сохранить. Время O(n + m), память результата O(n + m). Выход нельзя накладывать на входные диапазоны; back_inserter добавляет элементы, а не записывает за пределами пустого vector.