Сортировка слиянием
Сортировка слиянием превращает одну трудную задачу во много простых: два отсортированных списка легко объединить в один. Делите список пополам, пока каждый кусок не станет одним значением, затем слейте куски обратно. Это классический алгоритм «разделяй и властвуй», и его время — n log n при любых входных данных.
Идея
Слияние — простая часть. Если есть два списка и каждый отсортирован, сравните их первые значения и возьмите меньшее. Сравните новые первые значения и снова возьмите меньшее. Когда один список закончится, допишите остаток другого. Каждый шаг забирает одно значение, поэтому слияние двух списков общей длины m требует не больше m − 1 сравнений. Сортировка слиянием использует это для сортировки: разделите список пополам, отсортируйте каждую половину сортировкой слиянием и слейте две половины.
Пример
Возьмём 5, 1, 4, 2, 8. Делим на 5, 1 и 4, 2, 8. Первая половина делится на 5 и 1, которые сливаются в 1, 5. Вторая половина делится на 4 и 2, 8; 2, 8 получается слиянием 2 и 8, затем сливается с 4 в 2, 4, 8. Наконец сливаются 1, 5 и 2, 4, 8: 1, затем 2, затем 4, затем 5, и остаётся 8. Это 8 сравнений, 12 записей и 4 слияния.
Почему n log n
Каждое деление уменьшает куски вдвое, поэтому примерно через log₂ n уровней каждый кусок — одно значение. На обратном пути каждый уровень слияний обрабатывает каждое значение один раз: n записей и меньше n сравнений на уровень. Всего это около n log₂ n. Для 40 значений сортировка делает 216 записей и не больше 177 сравнений; сортировке пузырьком для того же списка может понадобиться 780 сравнений. Порядок входных данных значит гораздо меньше, чем для таких сортировок: для 40 значений отсортированный список требует 100 сравнений, обратный — 116, а случайный — около 160.
Буфер и устойчивость
Чтобы слить две половины, стоящие рядом в списке, обычный способ копирует их в буфер и записывает обратно по порядку. Приложение показывает этот буфер вторым рядом столбиков. Ему нужно столько же дополнительной памяти, сколько занимает список, — это главная цена сортировки слиянием. Взамен сортировка устойчива: когда два первых значения равны, первым идёт значение из левой половины, так что равные значения сохраняют свой порядок. Устойчивость важна, когда записи сортируют сначала по одному полю, потом по другому.
История и применение
Джон фон Нейман (John von Neumann) описал сортировку слиянием в 1945 году, так что это один из первых алгоритмов, написанных для компьютера с хранимой программой. Поскольку она читает и записывает данные длинными сериями, она была стандартным способом сортировки данных на ленте и до сих пор применяется для файлов, слишком больших для памяти. Timsort, который используют Python и Java (для объектов), — это сортировка слиянием, которая сначала находит уже отсортированные серии, а короткие куски сортирует вставками.
Попробуйте сами
Откройте приложение и нажмите «Шаг». Затенённая часть списка сейчас делится или сливается, а пунктирная линия отмечает середину. Когда начинается слияние, обе половины опускаются в ряд буфера; два первых значения сравниваются, и меньшее поднимается обратно. Следите за счётчиками: записей одинаково для любого списка той же длины, а сравнений меньше всего для отсортированного или обратного списка и больше всего для случайного, но никогда не больше примерно n log₂ n.
Часто задаваемые вопросы
Какова временная сложность сортировки слиянием?
O(n log n) в лучшем, среднем и худшем случае. Обычной версии нужно O(n) дополнительной памяти для буфера.
Чем сортировка слиянием отличается от быстрой сортировки?
Обе делят список и сортируют части. Сортировка слиянием делит посередине, не глядя на значения, и выполняет работу при слиянии; быстрая сортировка выполняет работу при делении, перемещая значения вокруг опорного элемента, и слияние ей не нужно. Быстрая сортировка работает на месте и на практике часто быстрее, но на плохих данных может замедлиться до n² и не является устойчивой. Сортировка слиянием всегда n log n и устойчива.
Что такое восходящая сортировка слиянием?
Версия без рекурсии: сначала соседние одиночные значения сливаются в пары, затем пары в четвёрки и так далее, с удвоением длины в каждом раунде. Она выполняет ту же работу, что и показанная здесь нисходящая версия.
Устойчива ли сортировка слиянием?
Да, если при равенстве первым берётся значение из левой половины, как в этом приложении.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать сортировку слиянием