Algoritmos de Divide y Vencerás

Así se llama el tema 1 de la asignatura que ando cursando, Análisis y Diseño de Algoritmos 2. Anteayer tuvimos el exámen de la teoría de este tema y no me salió muy bien debido a mis problemas con la resolución de ecuaciones de recurrencia 🙁 Aun así hoy he continuado con los ejercicios de prácticas y al resolver el ejercicio 7 me han surgido unas dudas. Para los que conozcais este tipo de algoritmos sabreis que Ordenación por fusión y Ordenación rápida son 2 claros ejemplos. Pues el ejercicio en cuestión consistía en programarlos usando como tamaño umbral 8 para el primero y 4 para el segundo. Hasta aquí no ha habido problema. Pensando yo antes de llevar a cabo el ejercicio presupuse que al elevar el tamaño del umbral de 1 a los respectivos valores los tiempos que resultasen debian de ser mayores ya que el algoritmo usado por debajo de dicho umbral se supone peor que el existente en «la mayoría de los casos». Pero aquí estuvo mi sorpresa, no estaba en lo cierto, al aumentar el tamaño del umbral los tiempos han mejorado. Para que os hagais una idea en vectores de 50000 elementos se ha bajado los tiempos 2 centésimas de segundo 🙂 Supongo que esta mejora puede ser debida a que en vectores pequeños (de tamaño menor a 20), y dado que los umbrales siguen siendo bajos, el algoritmo de ordenación por inserción es mejor que el algoritmo general usado.