La ordenación superadaptativa contraataca.
Cada vez que pienso en ordenación y se me ocurre algo pienso que como lo hacía tan complicado, y que cómo lo complican tanto si es “tan fácil”.
Ordenar un vector de n elementos con k vectores ordenados en su interior, de forma óptima, viene a ser hallar en el mínimo tiempo posible la sorting network que caracteriza la ordenación de ese vector (por eso da igúal el tiempo de inserción suplementario a la búsqueda binaria, sólo ordenamos una vez que sabemos todas las relaciones entre elementos).
Ordenar un vector de n elementos con k vectores ordenados en su interior, el más largo de ellos de c elementos, es equivalente a ordenar los centros de de los k vectores (invocación recursiva al mismo algoritmo) y ordenar el elemento central a la izquierda del primer elemento ordenado con el central a la derecha del segundo ordenado etc… (búsqueda binaría de los centros de los k vectores en los demás de forma simultanea).
Mediante una búsqueda binaría simultanea masiva, de los elementos centrales de los k vectores, el coste sería:
ordenar(n)=(n-1)+ordenar(k)*log2(c)
En el peor caso (donde halla menos orden que aprovechar, vectores de 2 elementos)
ordenar(n)=(n-1)+ordenar( n/2)*log2(2)
P.D.: redondeando al entero superior log2(2)=1+1=2.