Forse un buon inizio è guardare la relazione di ricorrenza per questo problema. Immagino che per le tipiche Mergesort sarebbe simile a questa:
T(N) = 2 * T(N/2) + N
vale a dire che si sta dividendo il problema in sottoproblemi 2 della metà delle dimensioni, e quindi l'esecuzione di lavori N (l'unione). Abbiamo un caso base che richiede tempo costante.
Modellazione questo come un albero che abbiamo:
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)
Questo dà un ampliamento della
T(N) = N + 2N/2 + 4N/4 + ...
= N + N + N ...
Quindi, in realtà abbiamo solo bisogno di vedere quanto in profondità si va. Sappiamo che il livello i opera su sottoproblemi N/2^i di dimensioni. Così i nostri nodi foglia (T(1)) si verificano a livello L dove N/2^L = 1:
N/2^L = 1
N = 2^L
log N = log(2^L)
log N = L
Quindi il nostro tempo di esecuzione è N log N.
Ora introduciamo l'ordinamento di inserimento. Il nostro albero sarà simile a questa
T(N) = ... -> I(K)
-> I(K)
...x N/K
In altre parole, ci sarà a un certo livello L dover risolvere i problemi N/K insertion sort di dimensioni K. L'ordinamento di inserimento ha un runtime nel caso peggiore di K^2. Quindi, le foglie che hanno questo molto lavoro in totale:
(N/K) * I(K)
= (N/K) * K * K
= N * K
ma abbiamo anche un po 'di fusione di fare così, ad un costo di N per ogni livello dell'albero come spiegato in precedenza. Tornando al nostro metodo precedente, troviamo L (il numero di livelli prima di raggiungere sottoproblemi di dimensione K e quindi passare a inserimento):
N/2^L = K
N/K = 2^L
L = log (N/K)
Quindi, in totale abbiamo
O(N) = N * K + N * log (N/K)
E 'stato troppo tempo da quando ho preso gli algoritmi per darti una bozza di prova, ma questo dovrebbe far esplodere i tuoi neuroni.