Quizás un buen comienzo sea ver la relación de recurrencia para este problema. Imagino para mergesort típica se vería algo como esto:
T(N) = 2 * T(N/2) + N
es decir, estás dividiendo el problema en subproblemas 2 de la mitad del tamaño, y luego realizar el trabajo N (la fusión). Tenemos un caso base que lleva tiempo constante.
Modelado esto como un árbol que tenemos:
T(N) = N -> T(N/2)
-> T(N/2)
= N -> (N/2) -> T(N/4)
-> T(N/4)
-> (N/2) -> T(N/4)
-> T(N/4)
Esto da una expansión de
T(N) = N + 2N/2 + 4N/4 + ...
= N + N + N ...
Así que en realidad sólo tenemos que ver qué tan profundo que va. Sabemos que el nivel i está en los subproblemas N/2^i. Así que nuestros nodos hoja (T(1)) se producen en el nivel L donde N/2^L = 1:
N/2^L = 1
N = 2^L
log N = log(2^L)
log N = L
Así que nuestro tiempo de ejecución es N log N.
Ahora presentamos la ordenación por inserción. Nuestro árbol se verá algo como esto
T(N) = ... -> I(K)
-> I(K)
...x N/K
En otras palabras, vamos a en algún nivel L tienen que resolver los problemas de inserción N/K especie de tamaño K. La ordenación por inserción tiene un tiempo de ejecución en el peor de los casos de K^2. Así que en las hojas que tienen esta cantidad de trabajo en total :
(N/K) * I(K)
= (N/K) * K * K
= N * K
Pero también tenemos un montón de fusión que hacer, así, a un costo de N por cada nivel del árbol como se ha explicado antes. Volviendo a nuestro método anterior, vamos a averiguar L (el número de niveles antes de llegar a subproblemas de tamaño K y por lo tanto cambiar a la inserción):
N/2^L = K
N/K = 2^L
L = log (N/K)
Así que en total tenemos
O(N) = N * K + N * log (N/K)
Ha sido demasiado tiempo desde que tomé algoritmos para darte un boceto a prueba, pero eso debería hacer que tus neuronas se activen.