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

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

Алгоритм тот же, что и для массивов, но акцент на слайсах Go: аллокации, ёмкость и отсутствие неожиданного разделения массива с входными данными.

Как отвечать

Каркас: два индекса, на каждом шаге берётся меньший элемент.

func mergeSorted(a, b []int) []int {
    res := make([]int, 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:]...)
}

Что здесь про Go, а не про алгоритм:

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

Сложность O(n+m) по времени и памяти. Короткая альтернатива slices.Sort(slices.Concat(a, b)) читается лучше, но это O(N log N) и лишняя работа на уже упорядоченных входах.

Слияние без аллокаций, если у первого слайса есть запас ёмкости: a = a[:len(a)+len(b)] и заполнение с конца, от больших элементов к меньшим. Аллокаций ноль, но входной слайс мутируется, и вызывающая сторона обязана про это знать; такую функцию называют соответственно.

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

Возвращают слайс, разделяющий массив с входным (a[:0] или срез аргумента), после чего вызывающий код получает испорченные данные при следующей записи в исходный слайс.