Как реализовать слияние двух отсортированных массивов в один отсортированный

Что проверяют

Умение написать слияние двумя указателями за линейное время и аккуратность на краях: пустые входы, хвост, равные элементы. Заодно смотрят, предложите ли вы предварительную аллокацию.

Как отвечать

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

func Merge[T cmp.Ordered](a, b []T) []T {
    res := make([]T, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            res = append(res, a[i])
            i++
        } else {
            res = append(res, b[j])
            j++
        }
    }
    res = append(res, a[i:]...)
    return append(res, b[j:]...)
}

Что здесь важно проговорить:

• make(..., 0, len(a)+len(b)) даёт одну аллокацию. Без заданной ёмкости append переаллоцирует по ходу: примерно до 256 элементов ёмкость удваивается, дальше растёт шагом около четверти, и каждый рост это новый массив плюс копирование.
• Сравнение <=, а не <. При равных ключах элемент берётся из первого входа, и слияние остаётся устойчивым. Для чисел разницы нет, для структур, сравниваемых по одному полю, разница видна.
• Хвост дописывается одним append(a[i:]...), под капотом это copy. Два отдельных цикла в конце не нужны.
• Дженерик по cmp.Ordered (Go 1.21) вместо копии функции на каждый тип. Для структур делают вариант с компаратором func(a, b T) int.

Сложность: время O(n+m), каждый элемент читается один раз; память O(n+m) под результат. Наивное «склеить и отсортировать» это O(N log N) и лишняя работа на уже упорядоченных данных.

Крайние случаи, которые проверяет интервьюер: один или оба входа пустые, диапазоны не пересекаются вовсе, все элементы равны, длины различаются на порядки. Последний случай стоит отметить отдельно: когда одна последовательность на порядки короче, выгоднее вставлять её элементы через бинарный поиск, это O(m log n) вместо O(n+m).

Если результат надо разместить в первом слайсе, у которого есть запас ёмкости, слияние делают с конца, справа налево: иначе запись затрёт ещё не прочитанные элементы.

Где спотыкаются

Пишут условие for i < len(a) || j < len(b) и выходят за границы, либо забывают дописать хвост и молча теряют элементы, когда входы разной длины.