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

Условие

Необходимо реализовать функцию mergeSorted(a, b []int) []int, которая:

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

import "fmt"

func main() {
    var first = []int{1, 5, 6, 18, 99}
    var second = []int{2, 4, 9, 11}
    fmt.Println(mergeSorted(first, second))
}

func mergeSorted(first []int, second []int) []int {
    // реализация задачи
}

Ответ

Сливайте срезы двумя индексами: сравнивайте текущие элементы и переносите меньший. Для примера получится [1 2 4 5 6 9 11 18 99].

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

func mergeSorted(first, second []int) []int {
    out := make([]int, 0, len(first)+len(second))
    i, j := 0, 0
    for i < len(first) && j < len(second) {
        if first[i] <= second[j] {
            out = append(out, first[i])
            i++
        } else {
            out = append(out, second[j])
            j++
        }
    }
    out = append(out, first[i:]...)
    out = append(out, second[j:]...)
    return out
}

Время O(len(first)+len(second)), память нового результата того же порядка. Повторы сохраняются, исходные срезы не меняются. Пустой вход допустим: остаток другого среза копируется в результат.