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

Question

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

Тип вопроса: Golang Вероятность: 10% Категория: Golang Разработчик

Ответ

Для этой задачи используется алгоритм слияния (Merge Algorithm), который является частью сортировки слиянием (Merge Sort). Его суть заключается в итеративном сравнении элементов из обоих массивов с помощью двух указателей.

Принцип работы

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

Реализация в Go

// mergeSortedSlices объединяет два отсортированных слайса в один.
func mergeSortedSlices(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++
        }
    }

    // Добавляем оставшиеся элементы из любого из слайсов.
    // Только один из этих вызовов append фактически что-то добавит.
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Анализ сложности

Временная сложность: O(n + m), где n и m — длины массивов. Это оптимально, так как мы должны как минимум один раз просмотреть каждый элемент.
Пространственная сложность: O(n + m), так как мы создаем новый массив для хранения результата.

Ответ 18+ 🔞

Да ты посмотри, какая хуйня! Сливать два отсортированных массива — это ж классика, блядь, как «Муму» у Тургенева, только без утоплений, слава богу.

Вот представь: у тебя есть два ряда солдатиков, каждый ряд уже по росту выстроен. И тебе надо их в один общий строй поставить, чтобы тоже по росту шли. Ну и как, думаешь, самый тупой способ — это всех в кучу сгрести и заново сортировать? Да хуй там, это же O(n log n) получится, ёпта! Нам же надо O(n + m), чтобы быстро, как Герасим метаться начал, когда совесть заебала.

Так вот, алгоритм слияния — он как раз про это. Берёшь два указателя, i и j, ставишь их в начало каждого массива. И начинаешь сравнивать: кто меньше, того первым в новый массив и пихаешь, а его указатель на шаг вперёд. И так, пока один из рядов солдатиков не кончится. А потом просто остатки из того, что не доели, дописываешь в хвост — они и так самые большие будут, им всё равно.

Смотри, как на Go это выглядит, блядь:

// mergeSortedSlices объединяет два отсортированных слайса в один.
func mergeSortedSlices(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)! Потому что каждый элемент мы ровно один раз посмотрели и один раз запихнули. И памяти жрём ровно столько, сколько нужно под итоговый массив. Красота, ёпта, а не алгоритм. Проще, чем Герасиму собаку утопить, честное слово.