Сравнения
Записи
Слияния

  • Сливаемая часть
  • Сравниваются
  • Записаны обратно
  • Уже слито

Подробнее о сортировке слиянием

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

Сортировка слиянием — алгоритм «разделяй и властвуй». Она делит список пополам, так же сортирует каждую половину и сливает две отсортированные половины, каждый раз беря меньшее из первых значений. Смотрите, как половины переносятся в ряд буфера и записываются обратно по порядку, с любой скоростью или шаг за шагом, и считайте сравнения, записи и слияния. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти шаг за шагом. Перетащите ползунок шагов, чтобы перейти в любое место. Плитки считают сравнения, записи обратно в список и слияния. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

Как это работает

  1. Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
  2. Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться шаг за шагом. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
  3. Следите за каждым слиянием: две отсортированные половины опускаются в буфер, а меньшее из первых значений по одному поднимается обратно.

Как работает сортировка слиянием

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

Всегда n log n

Деление пополам снова и снова даёт примерно log₂ n уровней, и каждый уровень слияний записывает каждое значение один раз, поэтому сортировка делает около n log₂ n записей и не больше стольких же сравнений. В отличие от сортировки пузырьком, выбором и вставками, это число не растёт как n², а порядок списка значит гораздо меньше. Цена — буфер длиной со список. Сортировка слиянием ещё и устойчива, поэтому она лежит в основе сортировок в Python и Java.

Часто задаваемые вопросы

Как работает сортировка слиянием?

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

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

Для n значений — не больше примерно n log₂ n − n + 1 и не меньше примерно половины n log₂ n. Для 40 значений это не больше 177. Число записей обратно в список для данного n всегда одно и то же: по одной на значение на каждом уровне слияния.

Зачем сортировке слиянием дополнительная память?

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

Устойчива ли сортировка слиянием?

Да. Когда два первых значения равны, первым идёт значение из левой половины, поэтому равные значения сохраняют исходный порядок.

Мои числа куда-то отправляются?

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

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор