Как объединить два отсортированных массива в один отсортированный массив?

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

Это классическая задача на алгоритмы, часто встречающаяся на собеседованиях. Существует несколько подходов, отличающихся по сложности и эффективности.

Основные подходы

1. Наивный метод (слияние с последующей сортировкой)

Самый простой, но наименее эффективный способ — объединить массивы и отсортировать результат:

func mergeNaive(arr1, arr2 []int) []int {
    merged := make([]int, len(arr1)+len(arr2))
    copy(merged, arr1)
    copy(merged[len(arr1):], arr2)
    
    // Используем стандартную сортировку
    sort.Ints(merged)
    return merged
}

Недостатки:

• Сложность O((n+m)log(n+m)) из-за сортировки
• Не использует факт, что исходные массивы уже отсортированы

2. Алгоритм слияния (Two-pointer approach)

Оптимальное решение со сложностью O(n+m) и использованием факта отсортированности массивов:

func mergeSortedArrays(arr1, arr2 []int) []int {
    n, m := len(arr1), len(arr2)
    result := make([]int, n+m)
    
    i, j, k :=议会, 0, 0
    
    // Проходим по обоим массивам одновременно
    for i < n && j < m {
        if arr1[i] <= arr2[j] {
            result[k] = arr1[i]
            i++
        } else {
            result[k] = arr2[j]
            j++
        }
        k++
    }
    
    // Добавляем оставшиеся элементы из первого массива
    for i < n {
        result[k] = arr1[i]
        i++
        k++
    }
    
    // Добавляем оставшиеся элементы из второго массива
    for j < m {
        result[k] = arr2[j]
        j++
        k++
    }
    
    return result
}

Расширенная реализация с поддержкой generics (Go 1.18+)

func MergeSorted[T constraints.Ordered](arr1, arr2 []T) []T {
    result := make([]T, len(arr1)+len(arr2))
    i, j, k := 0, 0, 0
    
    for i < len(arr1) && j < len(arr2) {
        if arr1[i] <= arr2[j] {
            result[k] = arr1[i]
            i++
        } else {
            result[k] = arr2[j]
            j++
        }
        k++
    }
    
    // Копируем остатки
    copy(result[k:], arr1[i:])
    copy(result[k+len(arr1)-i:], arr2[j:])
    
    return result
}

Варианты и оптимизации

In-place слияние (для массивов с дополнительным пространством)

func mergeInPlace(arr1, arr2 []int) {
    // Предполагаем, что arr1 имеет достаточно места
    i, j := len(arr1)-len(arr2)-1, len(arr2)-1
    k := len(arr1)-1
    
    for j >= 0 {
        if i >= 0 && arr1[i] > arr2[j] {
            arr1[k] = arr1[i]
            i--
        } else {
            arr1[k] = arr2[j]
            j--
        }
        k--
    }
}

Рекурсивный подход (менее эффективный, но поучительный)

func mergeRecursive(arr1, arr2 []int) []int {
    if len(arr1) == 0 {
        return arr2
    }
    if len(arr2) == 0 {
        return arr1
    }
    
    if arr1[0] <= arr2[0] {
        return append([]int{arr1[0]}, mergeRecursive(arr1[1:], arr2)...)
    }
    return append([]int{arr2[0]}, mergeRecursive(arr1, arr2[1:])...)
}

Производительность и практические соображения

Ключевые моменты для собеседования:

1. Сложность алгоритма: оптимальное решение имеет временную сложность O(n+m) и пространственную O(n+m)
2. Стабильность: алгоритм слияния сохраняет относительный порядок равных элементов
3. Практическое применение: используется в сортировке слиянием (merge sort), слиянии отсортированных списков в базах данных
4. Параллелизация: алгоритм можно распараллелить для очень больших массивов

// Пример использования с бенчмарком
func BenchmarkMerge(b *testing.B) {
    arr1 := makeSortedArray(1000)
    arr2 := makeSortedArray(1000)
    
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        mergeSortedArrays(arr1, arr2)
    }
}

Распространённые ошибки

• Неправильная обработка оставшихся элементов после основного цикла
• Использование append в цикле (ведёт к многократным аллокациям)
• Неучёт пограничных случаев (пустые массивы, массивы разной длины)

Заключение

Алгоритм слияния двух отсортированных массивов — фундаментальная задача, демонстрирующая понимание:

• Указателей или индексов для одновременного обхода нескольких коллекций
• Асимптотической сложности алгоритмов
• Эффективной работы с памятью в Go
• Обработки edge cases

На практике в Go часто используют готовые решения, но понимание алгоритма критически важно для оптимизации производительности в реальных системах, особенно при работе с большими объемами данных.