Как работает слияние и почему MergeSort имеет сложность O(n log n)?

Слияние объединяет два уже отсортированных массива в один, каждый раз выбирая меньший из текущих первых элементов. Это линейная операция, потому что каждый элемент переносится ровно один раз. Сортировка слиянием строит из неё рекурсивный алгоритм «разделяй и властвуй».

Два указателя

Индексы i и j показывают первые ещё не перенесённые элементы левой и правой частей. Меньший элемент отправляется в результат, соответствующий индекс увеличивается. Когда одна часть закончилась, остаток другой копируется целиком; без этого шага хвост пропадёт.

Инвариант слияния

Перед каждой итерацией результат содержит наименьшие элементы двух исходных частей в правильном порядке, а позиции до i и j уже обработаны. Выбор меньшей текущей границы сохраняет сортировку. Равные элементы берут сначала из левой части, если требуется стабильность.

Рекурсивное деление

Массив делят примерно пополам, сортируют обе половины тем же способом и сливают. База — часть длины ноль или один, уже отсортированная. Глубина деления составляет около log₂ n уровней, потому что размер на каждом шаге уменьшается вдвое.

Оценка ресурсов

На каждом уровне рекурсивного дерева все слияния суммарно обрабатывают n элементов. Уровней O(log n), поэтому время равно O(n log n) даже для обратного порядка. Классическая реализация использует дополнительный буфер O(n) и стек рекурсии O(log n).

Проверка реализации

Протрассируйте нечётную длину, повторяющиеся элементы и уже отсортированный вход. Убедитесь, что границы половин не перекрываются и не оставляют пробела. На устной защите выведите сложность через «работа уровня × число уровней», а стабильность объясните правилом выбора при равенстве.

Слияние — линейная основа всей сортировки

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

def merge(left: list[int], right: list[int]) -> list[int]:
    result: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

def merge_sort(values: list[int]) -> list[int]:
    if len(values) < 2:
        return values.copy()
    middle = len(values) // 2
    return merge(merge_sort(values[:middle]), merge_sort(values[middle:]))

Дерево деления имеет логарифмическую высоту, а каждый уровень суммарно обрабатывает n элементов: O(n log n). Представленная версия выделяет дополнительную память для срезов и результата.

Практика: доказательство и стабильность MergeSort

Протрассируйте деление и слияние списка [7, 2, 5, 2, 9, 1]. Докажите корректность merge через инвариант указателей, затем корректность всей сортировки индукцией по длине. Замените <= на < и проверьте пары с одинаковым ключом и разными метками: как изменится стабильность? В дополнительной части подсчитайте число сравнений на степенях двойки и сопоставьте рост с n log₂n.