Что хотят услышать интервьюеры:

Нужно объяснить классический алгоритм merge: пройти по двум массивам двумя указателями и на каждом шаге брать меньший текущий элемент. Это даёт линейную сложность по сумме длин массивов и не требует дополнительной сортировки. Важно отдельно упомянуть обработку хвоста того массива, который не закончился.

Определение:

Слияние двух отсортированных массивов — это операция, при которой из двух уже упорядоченных последовательностей строится одна тоже упорядоченная последовательность. Обычно используется два индекса: по одному на каждый массив. На каждом шаге сравниваются текущие элементы, меньший переносится в результат, и соответствующий индекс сдвигается.

Пример использования:

Допустим, есть два отсортированных массива:

a := []int{1, 3, 5, 8}
b := []int{2, 4, 6, 7, 9}

Результат слияния:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Пример реализации на Go:

package main

import "fmt"

func mergeSorted(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
}

func main() {
	a := []int{1, 3, 5, 8}
	b := []int{2, 4, 6, 7, 9}

	fmt.Println(mergeSorted(a, b))
}

Пояснение кода:

Код не требуется, но пример разберём по шагам.

Создаётся результирующий слайс с ёмкостью len(a)+len(b), чтобы не делать лишних перераспределений памяти.
Два указателя i и j стартуют с нулевых позиций в a и b.
Пока оба массива не закончились, сравниваются a[i] и b[j].
Меньший элемент добавляется в result, после чего соответствующий индекс увеличивается.
Когда один массив заканчивается, оставшиеся элементы второго массива уже гарантированно идут в правильном порядке, поэтому они просто дописываются в конец результата.
В конце получается один отсортированный массив без дополнительной сортировки.

Ключевые моменты:

Алгоритм работает за O(n + m), где n и m — длины массивов.
Дополнительная память обычно O(n + m) для результата.
Если нужны дубликаты, они сохраняются как есть; если нужен merge без повторов, это отдельная логика.
Для стабильности при равных значениях обычно берут элемент из первого массива первым.
Метод подходит только для уже отсортированных входных данных.

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