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

Для слияния двух отсортированных массивов в один отсортированный можно использовать алгоритм слияния, похожий на тот, что применяется в сортировке слиянием (merge sort).

Идея:

• Идти по обоим массивам с двумя индексами.
• На каждом шаге сравнивать текущие элементы и добавлять меньший в результирующий массив.
• Когда один из массивов закончится, добавить оставшиеся элементы другого массива.

Пример на Go:

func mergeSortedArrays(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(n + m), где n и m — размеры входных массивов.