Объединение двух упорядоченных массивов в один

Условие

Реализовать функцию, принимающую два уже отсортированных массива, и возвращающую новый массив, в котором элементы обеих входных последовательностей расположены в отсортированном порядке.

Ответ

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

func merge(_ first: [Int], _ second: [Int]) -> [Int] {
    var i = 0, j = 0
    var result: [Int] = []
    while i < first.count && j < second.count {
        if first[i] <= second[j] {
            result.append(first[i]); i += 1
        } else {
            result.append(second[j]); j += 1
        }
    }
    while i < first.count { result.append(first[i]); i += 1 }
    while j < second.count { result.append(second[j]); j += 1 }
    return result
}

Предполагается сортировка по возрастанию. Дубликаты сохраняются, исходные массивы не меняются. Время O(n+m), память под результат O(n+m); повторно сортировать объединённый массив не требуется.