- Сливаемая часть
- Сравниваются
- Записаны обратно
- Уже слито
Сортировка слиянием
Сортировка слиянием — алгоритм «разделяй и властвуй». Она делит список пополам, так же сортирует каждую половину и сливает две отсортированные половины, каждый раз беря меньшее из первых значений. Смотрите, как половины переносятся в ряд буфера и записываются обратно по порядку, с любой скоростью или шаг за шагом, и считайте сравнения, записи и слияния. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти шаг за шагом. Перетащите ползунок шагов, чтобы перейти в любое место. Плитки считают сравнения, записи обратно в список и слияния. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться шаг за шагом. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
- Следите за каждым слиянием: две отсортированные половины опускаются в буфер, а меньшее из первых значений по одному поднимается обратно.
Как работает сортировка слиянием
Одно значение уже отсортировано. Более длинный список разделите на две половины и отсортируйте каждую сортировкой слиянием. Затем слейте их: посмотрите на первое значение каждой половины, перенесите меньшее в результат и повторяйте, пока обе половины не опустеют. Раз обе половины отсортированы, результат тоже отсортирован.
Всегда n log n
Деление пополам снова и снова даёт примерно log₂ n уровней, и каждый уровень слияний записывает каждое значение один раз, поэтому сортировка делает около n log₂ n записей и не больше стольких же сравнений. В отличие от сортировки пузырьком, выбором и вставками, это число не растёт как n², а порядок списка значит гораздо меньше. Цена — буфер длиной со список. Сортировка слиянием ещё и устойчива, поэтому она лежит в основе сортировок в Python и Java.
Часто задаваемые вопросы
Как работает сортировка слиянием?
Она делит список пополам, сортирует каждую половину сортировкой слиянием и сливает две отсортированные половины, каждый раз беря меньшее из их первых значений. Список из одного значения уже отсортирован, поэтому на нём деление останавливается.
Сколько сравнений делает сортировка слиянием?
Для n значений — не больше примерно n log₂ n − n + 1 и не меньше примерно половины n log₂ n. Для 40 значений это не больше 177. Число записей обратно в список для данного n всегда одно и то же: по одной на значение на каждом уровне слияния.
Зачем сортировке слиянием дополнительная память?
Быстро слить две половины на месте трудно, поэтому обычная сортировка слиянием копирует половины в буфер и записывает их обратно по порядку. Буфер длиной со список — главный недостаток по сравнению с быстрой и пирамидальной сортировкой.
Устойчива ли сортировка слиянием?
Да. Когда два первых значения равны, первым идёт значение из левой половины, поэтому равные значения сохраняют исходный порядок.
Мои числа куда-то отправляются?
Нет. Сортировка работает в вашем браузере, а последние настройки остаются в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор