#merge #language-agnostic #mergesort
#слияние #не зависит от языка #сортировка слиянием
Вопрос:
То, как я узнал или видел, как реализована сортировка слиянием, всегда было рекурсивным подходом сверху вниз, который требует O (n) дополнительной памяти.
Кажется, что при подходе снизу вверх вы можете сделать это с постоянной памятью. Операция слияния идентична нисходящему подходу. Поэтому мне кажется, что снизу вверх превосходит сверху вниз.
Почему подход сверху вниз чаще используется и преподается?
Комментарии:
1. вы можете принять ответ, нажав на серую галочку под его оценкой.
Ответ №1:
Чаще преподается сортировка сверху вниз, но в библиотеках чаще используется сортировка снизу вверх или, точнее, гибрид сортировки вставкой и сортировки слиянием снизу вверх.
Накладные расходы на пространство для второго буфера одинаковы как для обычной сортировки слиянием сверху вниз, так и снизу вверх O (n). Накладные расходы стека для сверху вниз равны O (log2 (n)).
Существуют варианты сортировки слиянием, в которых используется второй буфер меньшего размера или второй буфер отсутствует.
Комментарии:
1. Почему чаще используется «снизу вверх»?
2. @roulette01 — Частично устаревшая проблема, ранние версии сортировки слиянием были реализованы в системах без стека. Я не знаю, когда была изобретена сортировка слиянием сверху вниз или почему. Естественная сортировка слиянием, которая ищет существующие отсортированные прогоны данных, по своей сути является восходящей. timsort аналогичен, но использует стек для отслеживания прогонов способом, не поддерживающим стабильность (сохраняя равные элементы в их первоначальном порядке). Снизу вверх немного быстрее, чем сверху вниз, но разница настолько мала, что я сомневаюсь, что это фактор.
3. Ах. Я понимаю. По какой-то причине я думал, что снизу вверх — это O (1) пробел, но, очевидно, это все еще O (n) из-за операции слияния, на которую вы ссылались (хотя сложность пространства все еще немного лучше, потому что вы больше не накапливаете стек рекурсии). Я слышал, что есть какое-то решение для сортировки слиянием в пространстве O (1), но я никогда не изучал его.
4. @roulette01 — O (1) алгоритмы сортировки слиянием в пространстве в наши дни в основном являются академическими усилиями. Код может быть сложным, как в этом примере, который может работать с небольшим буфером grail или без него. Сортировка слиянием github . Взгляните на GrailSort.h .
5. В библиотеках часто используется Buttom-up, поскольку накладные расходы на вызов функции в рекурсивной реализации являются значительными затратами.