¿Cuándo cambia introsort de quicksort a heapsort?

Introsort comienza con quicksort y cambia a heapsort cuando la profundidad de la recursión supera un nivel basado en la cantidad de elementos que se ordenan. ¿Cuál es ese número? ¿Hay un rango específico o un valor límite?

Respuestas a la pregunta(2)

Acabo de intentar leer la introducciónArtículo de Wikipedia. Dice

Cuenta la profundidad de la recursión. Si se excede una profundidad logarítmica, el algoritmo cambia a Heapsort desde Quicksort para mantener el resultado de peor caso de Quicksort abajo

ya través del artículo original de Musser sobre Introsort.

Dice que introsort es más lento que heapsort porque realiza 2 * log (2, N) cálculos antes de que cambie a heapsort.

Mi entendimiento es que la profundidad de la recursión es 2 * log (2, N)

Para N = 300 elementos a ordenar, será 2 * 8 = 16

 this12 oct. 2013 06:55
Si utiliza el límite de profundidad de 16 en una serie de 300 elementos a aproximadamente el nivel de profundidad 10, el subarreglo tendrá 0 elementos.
Solución de preguntas

El punto en el que elAlgoritmo introsort los cambios de Quicksort a Heapsort están determinados pordeep_limit:

deep_limit = 2 · ⎣log2(l) ⎦

Dóndel es la longitud de la secuencia que se va a ordenar, por lo quel‍ = ‍n Para toda la secuencia. Con cada llamada recursivadeep_limit Se decrementa en uno. Cuandodeep_limit llega a 0, cambia de Quicksort a Heapsort.

 this12 oct. 2013 15:23
Lee mi comentario a continuación; otro ejemplo: la matriz de 10000 miembros tendría un límite de profundidad de (13 * 2), si la matriz se dividiera aproximadamente por la mitad en cada recursión, en el nivel 14 los subconjuntos tendrán 0 elementos.
 Gumbo12 oct. 2013 08:38
@yo. ¿Por qué piensas eso?
 this12 oct. 2013 06:53
Según su lógica, el Heapsort nunca sucederá, ya que nunca se alcanzará el límite de profundidad.
 Gumbo12 oct. 2013 16:14
@yo. Bueno, dividir por la mitad es el mejor de los casos; en el peor de los casos, la secuencia se dividirá en (1, N-1). En ese caso depth_limit llega a 0.

Su respuesta a la pregunta