Финальный массив после слияния

Условие

После завершения основного цикла слияния необходимо добавить оставшиеся элементы одного из векторов в итоговый массив, избегая дополнительных проверок.

std::vector<int> merged{};
merged.reserve(first.size() + second.size());

size_t i = 0, j = 0;
while (i < first.size() && j < second.size()) {
    if (first[i] > second[j]) {
        merged.push_back(second[j++]);
    } else {
        merged.push_back(first[i++]);
    }
}

Ответ

Добавьте оба оставшихся диапазона через insert: у исчерпанного вектора диапазон будет пустым. Дополнительное ветвление для выбора остатка не требуется.

После основного цикла:

merged.insert(merged.end(), first.begin() + i, first.end());
merged.insert(merged.end(), second.begin() + j, second.end());

Один из индексов уже равен размеру своего вектора, поэтому соответствующий insert ничего не добавит. Работает и для пустых входов. Предполагается, что merged — отдельный контейнер, а оба входа отсортированы.

Полная сложность слияния O(n + m); предварительный reserve сокращает перевыделения, но для очень больших размеров сумму ёмкостей нужно защищать от переполнения.