← Volver a los ejercicios

Ordenar 20 millones partiendo en dos: cuántos hilos y cuál mezcla corre sola

La recursión de ordenar_par dibujada por niveles. Elija hasta qué profundidad se lanzan hilos, prediga cuántos nacen y después recorra los pasos en el orden en que el código los ejecuta.

1. El árbol según la profundidad de corte

ahora 2
hilo nuevo el hilo que ya venía hoja: se ordena de corrido
Cada división lanza un hilo para la mitad izquierda; la derecha la resuelve el hilo que ya estaba ahí. Una llamada deja de partir cuando se acaba el presupuesto de profundidad o cuando el trozo baja de 10.000 elementos.

2. Antes de mover la perilla

¿Cuántos hilos se crean con profundidad 3?

3. Paso a paso, en el orden del código

La traza sigue al hilo principal. Cada hilo lanzado repite el mismo recorrido por su cuenta; aquí se ve cuándo se lanza y cuándo el principal lo espera. Verde: rangos que ya quedaron ordenados.

4. Qué sucede al medirlo

ProfundidadHilosTiempoAceleración
Medido con taskset -c 0-3, cuatro núcleos. La versión secuencial tarda 2.227 ms y std::sort 1.469 ms sobre los mismos datos. La mezcla del nivel 0, medida aparte, 83 ms.

Con cuatro núcleos, ¿por qué ocho hilos (profundidad 3) aún ganan sobre cuatro (profundidad 2)?