Mergesort
Análise de complexidade no Mergesort:
editarNo 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:
editarO 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:
editar(*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];