Você pode mostrar que o tipo de fusão tem complexidade temporal [matemática]O(n \log n)[/math]?

Divide Step

Deixe haver um array de n elementos ... merge sort, sendo uma relação de recorrência do tipo dividir e conquistar, tende a pegar o array e dividi-lo em 2 subarranjas de igual tamanho (ou seja, subarranjas contendo n/2 elementos para um array de n elementos) recursivamente até que as subarranjas contenham apenas 1 elemento.

Este procedimento de divisão leva D(n)=2D(n/2) tempo--> n é dividido em 2 subarquetes de n/2 elementos.

P>Conquistar Passo

Na fase de conquista os primeiros elementos de cada subarquetes são comparados entre si e o elemento menor é colocado como o primeiro elemento do arrays pai. Então o antigo segundo elemento de um array torna-se seu elemento primário e é comparado com o primeiro elemento do segundo array. Este processo leva n-1 comparações em todos, já que o último elemento não precisa ser comparado.

This conquer procedure, hence, takes C(n) = n-1

Divide and Conquer

In total divide and conquer, thus, takes T(n)= D(n) + C(n) => T(n) = 2T(n/2) + n-1 => T(n) = 2T(n/2) + O(n)

Akra-Bazzi solution to the recurrence relation:

T(n)=2T(n/2) + n is a divide and conquer relation

where a = 2; b = 1/2;

Hence,

Step 1: we set p such that a*(b)^p = 1 => 2*(1/2)^1 = 1

Step 2: Plug p = 1 and g(u)=g(n)=n in: T(n) = θ(n + n ∫(n/n*n)du)
=> T(n) = θ(n + n∫(1/n)du) => T(n) = θ(n + n(lg n))

=> T(n) = θ ( n lg n)

Q.E.D.