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

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

8 ноября 2026Время чтения: 8 минут
#сортировка слиянием#сложность алгоритмов#алгоритмы сортировки#рекурсия#структуры данных
Сортировка слиянием: сложность по времени и памяти

Сортировка слиянием для массива из nn элементов в обычной реализации работает за Θ(nlog⁡n)\Theta(n\log n) времени и использует Θ(n)\Theta(n) дополнительной памяти. Она делит массив на части, сортирует каждую и объединяет результаты. Линейная работа слияния повторяется на логарифмическом числе уровней: именно из этого произведения возникает оценка. Она сохраняется для лучшего, среднего и худшего входа, если алгоритм всегда выполняет слияния и стоимость сравнения постоянна.

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

Как работают разделение и слияние

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

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

Например, при слиянии [2,6][2, 6] и [3,8][3, 8] сравниваются 22 и 33, затем 66 и 33, потом 66 и 88. Получается [2,3,6,8][2, 3, 6, 8]: оставшуюся восьмёрку сравнивать уже не нужно. На слияние частей общей длины mm требуется не более m−1m-1 сравнений ключей, а перенос всех элементов занимает Θ(m)\Theta(m) действий. При пустой части сравнения вообще не нужны.

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

Почему получается n log n

Пусть для начала n=2kn=2^k. На самом верхнем уровне одно слияние обрабатывает nn элементов. Уровнем ниже есть два слияния по n/2n/2 элементов, вместе опять nn. Ещё ниже - четыре по n/4n/4. В сумме на каждом уровне переносится nn элементов, а уровней слияния ровно k=log⁡2nk=\log_2 n.

Отсюда общая работа по переносу имеет порядок nlog⁡2nn\log_2 n. Разделение, вызовы и проверки границ также учитываются в общей оценке и не меняют её порядок. При последовательном выполнении базовая рекурсия записывается так:

T(n)=2T(n/2)+Θ(n),T(1)=Θ(1).T(n)=2T(n/2)+\Theta(n),\qquad T(1)=\Theta(1).

Идея решать меньшие подзадачи встречается и в алгоритме Карацубы, хотя его рекуррентное соотношение другое. Разворачивая соотношение сортировки по уровням, получаем T(n)=Θ(nlog⁡n)T(n)=\Theta(n\log n) для n≥2n\ge 2. Буква Θ\Theta здесь означает и верхнюю, и нижнюю границу одного порядка; подробнее разница между обозначениями разобрана в статье о временной и пространственной сложности. Вывод через рекурсию также приведён в учебных материалах MIT.

Если nn не степень двойки, половины имеют размеры ⌊n/2⌋\lfloor n/2\rfloor и ⌈n/2⌉\lceil n/2\rceil. Ветви заканчиваются на соседних глубинах, максимальная глубина равна ⌈log⁡2n⌉\lceil\log_2 n\rceil, а асимптотика остаётся Θ(nlog⁡n)\Theta(n\log n). Нельзя просто подставлять дробное число элементов в формулу точного счёта: для него нужны округления на каждом разбиении.

Сколько сравнений на конкретном массиве

Возьмём массив [8,3,6,2,7,4,5,1][8, 3, 6, 2, 7, 4, 5, 1]. После разбиения на отдельные элементы объединяем соседние части. Поскольку размер равен восьми, удобно посчитать сравнения по трём проходам снизу вверх:

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

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

Для n=2kn=2^k максимум сравнений удовлетворяет соотношению C(1)=0C(1)=0, C(n)=2C(n/2)+n−1C(n)=2C(n/2)+n-1. Его решение:

Cmax⁡(n)=nlog⁡2n−n+1.C_{\max}(n)=n\log_2 n-n+1.

При n=8n=8 формула даёт 8⋅3−8+1=178\cdot3-8+1=17. Для произвольного nn калькулятор применяет рекурсию к двум целым половинам. Максимум для слияния отрезка длины mm равен m−1m-1, минимум - длине меньшей половины; для полного алгоритма результаты складываются по дереву вызовов. Такой счёт относится к сравнениям ключей, а не к проверкам индексов или записи в память. Рекуррентный вывод максимума разобран в конспекте MIT по рекуррентным соотношениям.

Лучшая, средняя и худшая сложность

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

Однако формулировка зависит от реализации. Если перед слиянием проверять, не меньше ли первый элемент правой половины последнего элемента левой, уже упорядоченные соседние части можно оставить как есть. На полностью отсортированном массиве такая оптимизация в подходящей реализации даёт линейное время, хотя худший случай остаётся Θ(nlog⁡n)\Theta(n\log n). Это отличие важно при сравнении с калькулятором, где пропуска слияний нет. Идею проверки границы описывают и авторы курса Algorithms.

Сколько нужно дополнительной памяти

Для слияния массива обычно выделяют вспомогательный буфер на nn элементов и повторно используют его на разных уровнях. При последовательной обработке половин их буферы не обязаны одновременно занимать по nn мест на каждом уровне: пиковая дополнительная память буфера составляет Θ(n)\Theta(n). Стек рекурсии добавляет O(log⁡n)O(\log n) кадров, поэтому общая оценка остаётся Θ(n)\Theta(n).

Это именно пиковый расход сверх исходного массива. Суммарное количество записей в буфер за всё выполнение может быть Θ(nlog⁡n)\Theta(n\log n): повторное использование ячеек не означает, что данные записывались туда лишь однажды. В конкретной программе на расход также влияют копирование срезов, размер объектов и способ выделения памяти.

Существуют более сложные слияния на месте, но приведённая оценка относится к распространённому варианту с буфером. В пирамидальной сортировке массивов дополнительная память может быть O(1)O(1), зато она обычно неустойчива. В связном списке слияние можно организовать перестановкой ссылок, поэтому расходы памяти зависят и от структуры данных.

Устойчивость и сравнение с другими сортировками

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

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

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

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

  • Считать, что log⁡n\log n - цена одного слияния. Одно слияние линейно по суммарной длине частей; логарифм возникает из числа уровней.
  • Умножать размер буфера на глубину рекурсии. Повторно используемый буфер занимает Θ(n)\Theta(n) в пике, а не Θ(nlog⁡n)\Theta(n\log n).
  • Принимать 17 сравнений за число для любого массива из восьми элементов. Это максимум модели; минимум равен 12.
  • Считать устойчивость автоматической. Она зависит от правила обработки равных ключей и сохранения порядка в частях.
  • Переносить оценку на произвольную оптимизацию без оговорок. Пропуск уже упорядоченных слияний меняет лучший случай.

FAQ

Сортировка слиянием всегда работает за O(n log n)?

Обычная сбалансированная версия с линейным слиянием имеет такую верхнюю границу для любого входа при постоянной цене сравнения. Для неё справедлива и точная асимптотика Θ(nlog⁡n)\Theta(n\log n). Оптимизации могут улучшить лучший случай.

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

В принятой модели - от 12 до 17. Точное значение зависит от порядка ключей. Верхняя граница получается по формуле 8log⁡28−8+1=178\log_2 8-8+1=17.

Подходит ли алгоритм для стабильной сортировки?

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

Коротко

Сортировка слиянием обрабатывает все nn элементов на каждом из примерно log⁡2n\log_2 n уровней. Обычный вариант с буфером гарантирует Θ(nlog⁡n)\Theta(n\log n) времени и требует Θ(n)\Theta(n) дополнительной памяти; устойчивость обеспечивается выбором левого элемента при равенстве. Число сравнений зависит от входа и правил реализации.

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

Открыть EssayAI

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск в двоичном дереве поиска: алгоритм и сложность

Как работает поиск в двоичном дереве поиска (BST): пошаговый алгоритм, число сравнений в среднем и худшем случае, влияние баланса дерева и типичные ошибки в задачах.

11 июня 20267 минут