Почему интросорт использует heapsort, а не mergesort?

В рамках домашнего задания, посвященного реализации интросорта, меня спрашивают, почему используется heapsort, а не mergesort (или другие алгоритмы в этом отношении). $O(n\log(n))$

Интросорт - это гибридный алгоритм сортировки, который обеспечивает как быструю среднюю производительность, так и (асимптотически) оптимальную производительность в худшем случае. Он начинается с быстрой сортировки и переключается на heapsort, когда глубина рекурсии превышает уровень, основанный на (логарифме) числа сортируемых элементов. ( Википедия , получено 2014-May-06.)

Единственная причина, по которой я могу придумать, заключается в том, что heapsort «на месте» ... Но я не очень понимаю, почему это здесь имеет значение.

algorithms algorithm-analysis sorting user672009
источник

Если интросорт является частью вопроса, вам нужно будет сказать нам, что это, прежде чем мы сможем что-то сказать.

Луи

Добро пожаловать в информатику ! Обратите внимание, что вы можете использовать LaTeX здесь, чтобы набирать математику более читабельным способом. Смотрите здесь для краткого введения.

FrankW

Нас просто просят создать псевдокод для вступительной сортировки, и позже нас спрашивают, почему он использует heapsort, а не mergesort.

user672009

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

Рафаэль

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

user672009

Ответы:

2 недостатка быстрой сортировки в том, что она требует дополнительного пространства (для сохранения несортированных интервалов), и неправильный выбор пивота (или искусственные последовательности, предназначенные для выбора плохого пивота) может привести к тому, что он будет алгоритм времени и дополнительного пространства. $O(\log n)$ $O(n^2)$ $O(n)$

Переключение на heapsort, когда глубина рекурсии становится слишком большой (около ), означает, что у нас есть гарантированная верхняя граница, то есть времени и дополнительного пространства. $\log n$ $O(n \log n )$ $O( \log n)$

Пирамидальная сортировка в дополнительное требование пространства делает его лучшим выбором для mergsort в , где для надуманного массива, может быть еще большим. $O(1)$ $O(n)$ $n$

Причина, по которой heapsort не используется для полной сортировки, заключается в том, что она медленнее, чем быстрая сортировка (частично из-за скрытых констант в большом выражении O и частично из-за поведения кэша)

чокнутый урод
источник

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

user672009

Я подозреваю, что @ user672009 смущен вашим последним предложением. Я бы предложил уточнить, что интросорт не начинается с heapsort, потому что он медленнее.

Блуждающая логика

@ user672009, пробел означает «на месте», а быстрая сортировка не совсем на месте, потому что требует дополнительного пространства.

O (1)

$O(1)$

O (\lg n)

$O(\lg n)$

Блуждающая логика

Кроме того, в heapsort гораздо больше кеш-памяти, чем во внутренней сортировке.

noɥʇʎԀʎzɐɹƆ

Хорошая реализация Quicksort не требует места O (n) в худшем случае, если она запоминает больший подинтервал в стеке и обрабатывает меньшее сразу.

gnasher729