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

Условие

Даны два массива A и B, каждый из которых отсортирован по возрастанию и имеет длины M и N соответственно. Необходимо объединить их в один массив, упорядоченный по тем же правилам, содержащий все элементы исходных массивов.

Ответ

Два указателя позволяют слить массивы за O(M+N), каждый раз выбирая меньший из текущих элементов. Все повторы сохраняются.

После исчерпания одного массива остаток другого уже упорядочен и добавляется целиком.

func merge(a, b []int) []int {
    result := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)
    return result
}

Память результата O(M+N), дополнительные индексы O(1). Пустые массивы обрабатываются без отдельного случая. Алгоритм не сортирует неупорядоченный вход: возрастание каждого исходного массива — обязательное предусловие.