Mergesort

Análise de complexidade no Mergesort:

No Merge Sort para n = 1 temos T(1) = 1. A equação de recorrência para o Merge Sort é: T(n)=2T(n/2)+O(n)

O termo 2T(n/2) é o tempo para ordenar dois vetores de tamanho n/2, já o termo O(n) é o tempo para juntar esses dois vetores (o tempo do método merge).

Divisão e conquista no Mergesort:

O Mergesort utiliza o método divisão e conquista. Se o tamanho do vetor for maior que 1, então o algoritmo realizará a divisão do vetor através de chamadas recursivas até que o no final de toda a divisão só restem vetores unitários. Após essa primeira etapa, o algoritmo analisa os vetores unitários que estão ordenados e compara os valores através de um vetor auxiliar. Após essa etapa, os valores são lançados no vetor principal. Esses dois procedimentos são realizados até restarem dois vetores principais. O merge (união) fará uma análise desses dois vetores através de um vetor auxiliar, juntando eles de forma ordenada. Assim, essa é a execução do projeto de Divisão e conquista do Merge Sort.

Pseudo código:

(*MergeSort ordena as posições e, e+1,..., d-1, d da lista A*)

MergeSort (e,d)

{

if (e < d ){ ### Se início menor que o fim

meio = (e+d)/2; ### Divide o vetor ao meio

MergeSort (e, meio); ### Primeira parte do vetor que ficou a esquerda

MergeSort (meio+1, d); ### Segunda parte do vetor que ficou a direita

Merge (e, meio, d); ### União das partes

}

Merge (e, m, d) {

e = início, m= meio e d = fim do vetor

i = e; j = m+1; k = e; ### Faz o merge ordenando os elementos

i = Início da primeira parte do vetor que termina em meio

j = m + 1 = Início da segunda parte do vetor que termina em fim

k = e = Início da primeira parte do vetor que termina em meio

while(i < m) &&(j < d) do{

if(A [i] < A[j]) { ### Se a primeira parte vetor for menor que a segunda parte do vetor então...

B [k] = A [i]; ### Copia para o vetor auxiliar (B[k])o elemento da primeira parte do vetor

k++; i++;

} else{

B [k] = A [j]; ### Copia para o vetor auxiliar (B[k]) o elemento da segunda parte do vetor

k++; j++;

}

}

while(i < m) do{ ### Copia o resto da primeira parte se foi a segunda que finalizou

B [k] = A [i];

k++; i++;

}

while(j < d) do{ ### Copia o resto da segunda parte se foi a primeira que finalizou

B [k] = A [j];

k++; j++;

}

for (i = e; i < d; i++) ### Copia os elementos já ordenados do vetor auxiliar para o vetor original

A [i] = B [i];