Por que o introsort usa o heapsort em vez de mesclar?

Como parte de uma tarefa de lição de casa que abrange a implementação do introsort , perguntam-me por que o heapsort é usado em vez de mesclar (ou outros algoritmos nesse sentido). $O(n\log(n))$

O Introsort é um algoritmo de classificação híbrido que fornece desempenho médio rápido e (assintoticamente) o pior desempenho ideal. Ele começa com quicksort e alterna para heapsort quando a profundidade da recursão excede um nível com base no (logaritmo do) número de elementos que estão sendo classificados. ( Wikipedia , recuperado em 2014-maio-06).

A única razão pela qual consigo pensar é que o heapsort está "no lugar" ... Mas, na verdade, não entendo por que isso importaria aqui.

algorithms algorithm-analysis sorting user672009
fonte

Se introsort faz parte da pergunta, você terá que nos dizer o que é antes que possamos dizer qualquer coisa.

Louis

Bem-vindo à Ciência da Computação ! Observe que você pode usar o LaTeX aqui para digitar matemática de uma maneira mais legível. Veja aqui uma breve introdução.

FrankW

Simplesmente nos pedem para fazer algum pseudo-código para introdução, e mais tarde nos perguntam por que ele usa heapsort em vez de mesclar.

User672009

@ user672009 Nesse caso, escreva o código de qualquer um e veja o que encontrou. O motivo pode ou não estar relacionado ao desempenho.

Raphael

Concluí que, desde a classificação rápida, precisamos usar outro algoritmo de classificação no local. No entanto, estou aberto à entrada.

User672009

Respostas:

As duas desvantagens do quicksort é que ele requer espaço extra (para manter os intervalos não classificados) e a seleção de pivô ruim (ou sequências planejadas para fazer você selecionar um pivô ruim) pode causar um tempo e algoritmo de espaço extra. $O(\log n)$ $O(n^2)$ $O(n)$

Mudar para heapsort quando a profundidade da recursão se tornar muito grande (em torno de ) significa que temos um limite superior garantido que é tempo e espaço extra . $\log n$ $O(n \log n )$ $O( \log n)$

requisito de espaço extra do Heapsort faz com que seja uma melhor escolha mesclar onde para uma matriz artificial que ainda possa ser grande. $O(1)$ $O(n)$ $n$

O motivo pelo qual o heapsort não é usado para a classificação completa é porque é mais lento que o quicksort (devido em parte às constantes ocultas na grande expressão O e em parte ao comportamento do cache)

catraca arrepiante
fonte

Mas o heapsort é usado ... e suspeito que seja porque está no lugar como o quicksort.

User672009

Eu suspeito que @ user672009 esteja confuso com sua última frase. Sugiro esclarecer que o introsort não começa com heapsort porque é mais lento.

Wandering Logic

O (1)

$O(1)$

O (\lg n)

$O(\lg n)$

Além disso, o heapsort tem muito mais erros de cache do que o introsort.

26zɐɹƆ

Uma boa implementação do Quicksort não precisa de O (n) espaço, na pior das hipóteses, desde que se lembre do subintervalo maior da pilha e lide com o menor imediatamente.

gnasher729