Comparaciones de merge sort: peor caso y caso promedio

Devuelve el recuento exacto del peor caso, el valor esperado para un orden aleatorio uniforme, los niveles de fusión recursiva y n por logaritmo en base 2 de n como referencia. Así puede observar el crecimiento lineal-logarítmico y compararlo con el de algoritmos cuadráticos.

Qué cuenta la calculadora

El cálculo considera las comparaciones de orden entre elementos durante la fusión, la operación central del análisis habitual de merge sort. No incluye comprobaciones de índices, asignaciones, escrituras en matrices temporales, llamadas recursivas, reservas de memoria ni el trabajo interno de un comparador personalizado. Un solo elemento no requiere ninguna comparación. Con entradas mayores, el algoritmo divide el intervalo, ordena ambas partes y compara repetidamente sus primeros elementos pendientes. Fusionar grupos de a y b elementos requiere como máximo a más b menos una comparaciones, pues el último elemento restante se copia sin otra comparación. El peor caso combina esta regla en el árbol de particiones real, incluso cuando n no es potencia de dos. Por ello, n_log2_n sirve como escala, mientras que los otros campos ofrecen las estimaciones operativas.

Cómo se obtienen el peor caso y el promedio

La fórmula exacta del peor caso es n por el techo del logaritmo en base 2 de n, menos dos elevado a dicho techo, más uno. Describe un merge sort binario estándar con submatrices divididas del modo más equilibrado posible. El promedio es una esperanza sobre permutaciones uniformemente aleatorias de claves distintas. En cada fusión de tramos con a y b elementos, el número esperado es a más b, menos a dividido entre b más uno, menos b dividido entre a más uno. La calculadora suma recursivamente ese coste sobre el mismo árbol equilibrado y solo redondea el resultado mostrado a seis decimales. Una esperanza puede ser fraccionaria aunque cada ejecución haga un número entero de comparaciones. Las claves duplicadas, otros criterios de desempate, las secuencias naturales o los umbrales de inserción pueden modificar la cifra observada.

Cómo interpretar el resultado lineal-logarítmico

El valor n_log2_n muestra la escala lineal-logarítmica característica. Cada nivel adicional procesa los n elementos, pero el número de niveles solo crece de forma logarítmica. Los dos cocientes dividen las comparaciones estimadas entre n por logaritmo en base 2 de n y permiten ver cuánto se acercan las cifras concretas a esa referencia cuando n es mayor que uno. Son valores descriptivos, no pruebas de complejidad ni mediciones de hardware. El tráfico de memoria, las reservas, el coste del comparador, la caché y el entorno de ejecución pueden dominar el tiempo real. Pruebe tamaños situados justo antes y después de potencias de dos: allí cambia la profundidad recursiva y se aprecia por qué la notación O grande omite constantes y términos menores sin que estos dejen de importar para una entrada concreta.