Classificação de dados por Intercalação:
MergeSort
Principais Métodos

Classificação por Trocas

Classificação por Seleção

Classificação por Inserção

Classificação por Intercalação
Classificação por Intercalação


Caracteriza-se pela utilização do padrão de projeto
Divisão e Conquista.
Idéia básica (MergeSort): é muito fácil criar uma
sequência ordenada a partir de duas outras também
ordenadas.
Divisão e Conquista: MergeSort



Divisão: se S tem zero ou um elemento, retorna-se S (já está
ordenado). Em qualquer outro caso (S tem pelo menos 2
elementos), removem-se todos os elementos de S e colocam-se
em duas seqüências, S1 e S2, cada um contendo
aproximadamente a metade dos elementos de S;
Recursão: ordena-se recursivamente as seqüências S1 e S2;
Conquista: os elementos são colocados de volta em S, unindo
as seqüências S1 e S2 em uma seqüência ordenada.
Exemplo Divisão e Conquista (MergeSort)
85
24
63
45
17
31
96
50
17
24
31
45
50
63
85
96
85
24
63
45
17
31
96
50
24
45
63
85
17
31
50
96
85
24
63
45
17
31
96
50
24
85
45
63
17
31
50
96
45
17
31
96
50
85
24
63
45
17
31
96
50
85
24
63
(a) Fase de Divisão
(b) Fase de Conquista
Exemplo do Processo MergeSort
MergeSort: Junção ou Merge

Utiliza um vetor temporário (Vtemp) para
manter o resultado da ordenação dos 2 subvetores.
MergeSort: Junção ou Merge

Após a ordenação, o conteúdo de Vtemp é
transferido para o vetor.
MergeSort: Junção ou Merge

Número de operações críticas ?
MergeSort: Junção ou Merge
Visão Geral do Processo MergeSort
MergeSort (parte do pseudo-código)
Algoritmo merge(S1,S2,S):
{ Entrada: Seqüências ordenadas S1 e S2 e uma seqüência vazia de S, todos implementados como
arranjos. }
{ Saída: Seqüência ordenada S contendo os elementos de S1 e S2. }
i  j 0
enquanto i < S1.size() e j < S2.size() faça
se S1.get(i) <= S2.get(j) então
S.addLast(S1.get(j)) { copia o i-nésimo elemento de S1 para o final de S }
ii+1
senão
S.addLAst(S2.get(j)) { copia o j-nésimo elemento de S2 para o final de S }
jj+1
fimse
fimenquanto
enquanto i < S1.size() faça { copia os elementos restantes de S1 para S }
S.addLast(S1.get(i))
ii+1
fimenquanto
enquanto j < S2.size() faça { copia os elementos restantes de S2 para S }
S.addLast(S2.get(j))
j  j +1
fimenquanto
MergeSort em C
Exercício

Dado o vetor com as chaves [9 25 10 18 5
7
15
3], aplicar o método MergeSort para
ordená-lo crescentemente.
Considerações Finais

É possível implementar o Merge Sort utilizando
somente um vetor auxiliar ao longo de toda a
execução, tornando assim a complexidade de espaço
adicional igual a Θ(n).

É possível também implementar o algoritmo com
espaço adicional Θ(1).

Algoritmo criado por Von Neumann.

Comprovado matematicamente que é praticamente
impossível fazer um algoritmo mais eficiente.