EssayAI
Блог
Блог
Естественные науки

Сортировка слиянием: как работает merge sort

8 ноября 2026Время чтения: 8 минут
Сортировка слиянием: как работает merge sort

Сортировка слиянием, или merge sort, упорядочивает данные в два приёма: делит последовательность на части, а затем соединяет уже отсортированные части. Секрет в том, что при слиянии достаточно сравнивать только первые оставшиеся элементы двух половин. Алгоритм гарантирует время O(nlog⁡n)O(n\log n) и при обычной реализации массива использует дополнительный буфер размера O(n)O(n). В калькуляторе можно изменить длину примера и проследить, сколько сравнений приходится на каждый проход.

Как работает слияние двух половин

Предположим, что отдельно уже отсортированы последовательности [1,3,5,8][1, 3, 5, 8] и [2,4,6,7][2, 4, 6, 7]. Сравним первые элементы: 1<21 < 2, поэтому в результат идёт единица. Теперь сравниваем 33 и 22, забираем двойку, затем сравниваем 33 и 44. Каждый раз указатель продвигается только в той половине, откуда взяли элемент.

Отсортированные половины соединяются по одному элементу: золотая рамка отмечает выбранное число, а использованные числа бледнеют; затем показ возвращается к началу.

Когда одна половина закончилась, оставшийся хвост другой уже отсортирован и больше не нуждается в сравнениях ключей. В нашем примере финальное слияние даёт [1,2,3,4,5,6,7,8][1, 2, 3, 4, 5, 6, 7, 8] за семь сравнений. Общее правило: слияние непустых последовательностей длины aa и bb требует не более a+b−1a+b-1 сравнений, хотя может закончиться и раньше. Запись результата всё равно занимает линейное время по числу элементов.

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

Разделение и обратная сборка на примере

Начнём с массива [8,3,5,1,7,2,6,4][8, 3, 5, 1, 7, 2, 6, 4]. Если делить его пополам до отдельных элементов, каждый фрагмент длины один уже отсортирован. Теперь соседние фрагменты можно сливать, постепенно увеличивая размер упорядоченных блоков. Снизу вверх получаются такие проходы:

  1. Пары: [3,8][3,8], [1,5][1,5], [2,7][2,7], [4,6][4,6]. Каждая пара требует одного сравнения, всего четыре.
  2. Четвёрки: [1,3,5,8][1,3,5,8] и [2,4,6,7][2,4,6,7]. На два слияния уходит по три сравнения, всего шесть.
  3. Восемь элементов: обе четвёрки сливаются в итоговый массив за семь сравнений.
Четыре состояния массива: исходная последовательность, отсортированные пары, четвёрки и результат; на проходах выполнено 4, 6 и 7 сравнений
Четыре состояния массива: исходная последовательность, отсортированные пары, четвёрки и результат; на проходах выполнено 4, 6 и 7 сравнений

Итого для этих данных и именно такого способа слияния: 4+6+7=174+6+7=17 сравнений ключей. Это не универсальное число для любого массива из восьми элементов: если одна половина исчерпается раньше, сравнений будет меньше. Калькулятор считает их отдельно от копирования оставшихся элементов и показывает те же 17 при восьми элементах. Для нечётной длины непарный блок переносится на следующий проход без слияния.

Реализация на Python

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

def merge_sort(a):
    if len(a) <= 1:
        return a[:]
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    result = []
    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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

База рекурсии важна: пустой массив и массив из одного элемента уже упорядочены. После каждого вызова обе половины отсортированы, поэтому описанный выше инвариант гарантирует правильность их слияния. По той же причине после верхнего вызова упорядочен весь массив. Если элементы - записи, вместо сравнения самих объектов нужно сравнивать выбранные ключи.

Есть и нерекурсивный вариант: сначала сливать соседние блоки длины один, потом длины два, четыре и так далее. Именно его проходы показывает калькулятор. Он удобен, когда нужно явно управлять обходом и не использовать стек рекурсивных вызовов. При неравных размерах последних блоков второй блок может быть короче или вовсе отсутствовать.

Откуда берётся O(n log n)

Для n=2kn=2^k деление даёт k=log⁡2nk=\log_2 n уровней слияния. На каждом уровне все фрагменты вместе содержат nn элементов, и их слияние занимает O(n)O(n) времени. Поэтому общая работа составляет O(nlog⁡n)O(n\log n). То же следует из рекуррентного соотношения T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n) при T(1)=O(1)T(1)=O(1).

Если nn не степень двойки, размеры половин отличаются не более чем на единицу, а число уровней ограничено ⌈log⁡2n⌉\lceil\log_2 n\rceil. Оценка порядка роста сохраняется. В стандартной реализации, которая выполняет слияния на каждом уровне, время также ограничено снизу величиной порядка nlog⁡nn\log n: каждый уровень обрабатывает все элементы. Здесь предполагается, что сравнение и перемещение одного элемента имеют постоянную стоимость. Для длинных строк или тяжёлых записей стоимость отдельной операции тоже надо учитывать.

Для степени двойки можно уточнить именно верхнюю границу сравнений в этой простой схеме. На проходе с блоками длины 2j2^j каждое слияние использует не более 2j−12^j-1 сравнений, а таких слияний n/2jn/2^j. Значит, на проход приходится не более n−n/2jn-n/2^j сравнений. Суммирование по всем проходам даёт nlog⁡2n−n+1n\log_2 n-n+1. При n=8n=8 эта граница равна 24−8+1=1724-8+1=17: выбранный пример как раз достигает её. Граница не означает, что столько сравнений обязательно потребуется каждому входу. Она также не включает проверки индексов, выделение памяти и копирование: это отдельные операции.

Например, если обе половины уже разделены по значениям, как [1,2,3,4][1,2,3,4] и [5,6,7,8][5,6,7,8], итоговому слиянию достаточно четырёх сравнений. Оставшуюся правую половину затем копируют целиком. Поэтому число сравнений показывает конкретную трассу, а асимптотическая оценка описывает рост затрат при увеличении размера входа. Разницу особенно полезно помнить, когда экспериментируют с маленькими массивами: на них постоянные расходы могут перевесить различие оценок.

Гарантия относится и к худшему расположению входных данных: разбиение примерно пополам не зависит от выбранного опорного элемента. Для контраста, в худшем случае быстрой сортировки неудачные разбиения могут дать квадратичную работу. Это не означает, что merge sort всегда быстрее: на реальное время влияют копирование, доступ к памяти и конкретная реализация.

Память и устойчивость

Обычный merge sort для массива использует вспомогательный буфер на nn элементов, то есть O(n)O(n) дополнительной памяти; рекурсивный стек занимает O(log⁡n)O(\log n). Не нужно суммировать объёмы всех слияний за всё время как одновременно занятую память: один буфер можно использовать повторно. В приведённом коде создаются срезы и новые списки, но при последовательном выполнении рекурсии пиковая дополнительная память тоже имеет порядок O(n)O(n). Существуют специальные варианты с меньшей памятью, однако их устройство сложнее.

Устойчивость означает сохранение исходного порядка записей с равными ключами. Пусть записи с одинаковой оценкой идут как 5A5_A и 5B5_B, причём AA был раньше. Если они оказались в разных половинах, правило «при равенстве взять слева» сначала выдаст 5A5_A. При условии, что обе половины уже устойчиво отсортированы, это сохраняет порядок равных записей и во всём результате. Если при равенстве брать справа, такая гарантия пропадает.

Для сравнения, пирамидальная сортировка тоже гарантирует O(nlog⁡n)O(n\log n) в худшем случае, но стандартная версия сортирует массив на месте и не является устойчивой. Выбор зависит от того, важнее ли сохранить порядок равных ключей или ограничить дополнительную память.

Когда подходит сортировка слиянием

Метод удобен, когда важны предсказуемое время и устойчивость: например, при последовательной сортировке таблицы по нескольким полям. Устойчивый второй проход сохраняет прежний порядок внутри групп равных новых ключей. Для корректного результата нужен согласованный порядок сравнения ключей.

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

Частые ошибки

  • Сливать неотсортированные половины. Сравнение только их первых элементов правильно лишь после сортировки каждой половины.
  • Считать копирование хвоста сравнениями. После исчерпания одной стороны оставшиеся ключи уже не сравниваются друг с другом, хотя их надо записать.
  • Объявлять любой вариант устойчивым. При равных ключах стандартное устойчивое слияние выбирает левую запись; правило сравнения имеет значение.
  • Путать суммарный объём копирования с пиковой памятью. Данные проходят через уровни многократно, но рабочий буфер можно переиспользовать.

FAQ

Сколько сравнений нужно для восьми элементов?

В приведённом примере - 17. Число зависит от входного порядка и реализации: отдельное слияние останавливает сравнения, как только одна сторона опустела.

Можно ли выполнить сортировку слиянием без рекурсии?

Да. Итеративная версия сливает соседние блоки длины один, два, четыре и так далее, пока не останется один отсортированный блок.

Всегда ли нужен буфер размера массива?

Для обычной реализации слияния массивов - да, это стандартная плата за простой линейный проход и устойчивость. Для списков и специальных алгоритмов существуют другие варианты с иной организацией памяти.

Коротко

Сортировка слиянием строит большие отсортированные фрагменты из маленьких. Каждый проход обрабатывает все элементы, а число проходов логарифмически растёт с длиной входа. Стандартный алгоритм устойчив при выборе левого элемента в случае равенства, работает за O(nlog⁡n)O(n\log n) и использует O(n)O(n) дополнительной памяти для массива.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Односвязный список: операции и их сложность

Односвязный список: операции и их сложность

Односвязный список: как устроены узлы и ссылки, как выполнять поиск, вставку и удаление, сколько переходов они требуют и когда нужен указатель на хвост.

8 ноября 20269 минут
Сортировка слиянием: сложность по времени и памяти

Сортировка слиянием: сложность по времени и памяти

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

8 ноября 20268 минут
Сортировка связного списка слиянием: алгоритм

Сортировка связного списка слиянием: алгоритм

Как отсортировать односвязный список слиянием: разделение быстрым и медленным указателями, перестановка ссылок, устойчивость и оценка времени и памяти.

8 ноября 20269 минут
Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: как устроены узлы, как построить BST по ключам, выполнить обход и удалить элемент, от чего зависит высота и сложность операций.

8 ноября 20268 минут
Обходы двоичного дерева: порядки и примеры

Обходы двоичного дерева: порядки и примеры

Обходы двоичного дерева на одном примере: прямой, симметричный, обратный и по уровням. Как работают рекурсия, стек и очередь, какие результаты и сложность.

8 ноября 20268 минут
Префиксное дерево: как устроен бор строк

Префиксное дерево: как устроен бор строк

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

8 ноября 20268 минут