Merge

Antes de prosseguirmos, precisamos saber a complexidade de tempo do procedimento MERGE. É sabido que dá para se construir sem muito esforço um algoritmo que fazer intercalação de dois vetores de tamanho iguais, cada um deles ordenados, em . Para provar, propomos um algoritmo que faça isso e calcularemos a sua complexidade:

No algoritmo , acima o laco while mais externo garante que não haja sobreposição dos dois vetores que estão sendo. A cada iteração desse laço, os dois laços internos vão linearmente percorrendo e inserindo, ordenadamente, os elementos contidos nas respectivas partições de A que cada laço trata:

$$3(m-i+1)+3[j-(m+1)+1]+(j-i+1)=4(j-i+1)=O(n)$$