Merge Sort

•

UTFPR

1

0

1

0

Aleffer Rocha

12/11/2018

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Você viu 3, do total de 66 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Você viu 6, do total de 66 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Você viu 9, do total de 66 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

E aí, curtiu este material?

Ajude a incentivar outros estudantes a melhorar o conteúdo

Gostou desse material? Compartilhe! 🧡

Estrutura de Dados I

24.142 Materiais compartilhados

Baixe o app para aproveitar ainda mais

Leia os materiais offline, sem usar a internet. Além de vários outros recursos!

Prévia do material em texto

Prof. Aleffer Rocha
Utiliza da técnica de projeto de algoritmos chamada “divisão e
conquista”.
Divisão: O problema maior é dividido em problemas menores
sucessivamente de forma recursiva;
Conquista: Ordena-se o menor resultado da chamada
recursiva;
Combinação: Combina-se os resultados da conquista até que
o problema maior seja resolvido.
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
10
34 13
2
51
3 4
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
10
34 13
2
51
3 4
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
10
34 13
2
51
3 4
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
10
34 13
2
51
3 4
0 78
5
14
0
34
1
13
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
10
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
3
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
10
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
0
34
1
13
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
3
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
0
34
1
13
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
3
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
0
34
1
13
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
3
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
13 13
2
51
3 4
0 78
5
14
34 13 0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
0
34
1
13
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
3
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
13 13
2
51
3 4
0 78
5
14
34 13 0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
0
34
1
13
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
34 13 0
4
78
3
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
13 34
2
51
3 4
0 78
5
14
34 13 0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51
3 4
0 78
5
14
0
4
78
3
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
13 34
2
51
3 4
0 78
5
14
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
0
4
78
3
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
13 34
2
51 0 78
5
14
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
3
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
0
4
78
3
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
13 34
2
51 0 78
5
14
0
4
78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 2
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 2
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 2
34 13 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 2
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 2
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 2
13 13 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 20
13 13 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
20
13 13 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
20
13 34 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 20
13 34 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
10
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 203 4 5v[6] = 
34 13 51 0 78 14
10
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
10
13 34 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20
34 13 51
3 4 5
0 78 14
34 13
2
51 0 78
5
14
1
2
0
3 4 5v[6] = 
34 13 51 0 78 14
1 20
13 34 51
5
0 78 14
13 34
2
51 0 78
5
14
3 4
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 78 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
4 5
0 78 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 78 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 78 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 78 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 14 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 14 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 14 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 14 14
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 14 78
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 14 78
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
0 78
5
14
2
3 4
5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 14 78
0 78
5
14
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51
3 4 5
0 78 14
2 5v[6] = 
34 13 51 0 78 14
13 34 51
3 4 5
0 14 78
10 2
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
34 13 51 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 51 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 51 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 51 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 51 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 51 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 51 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 0 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 78 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
013 14 34 51 14
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 78
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 78
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 78
13 34 51 0 14 78
10 2 3 4 53 4 55
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 78
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
2 5v[6] = 
0 13 14 34 51 78
Início Merge(v[], ini, meio, fim)
v_aux[] = malloc(fim – ini + 1); 
aux_ini = ini;
aux_meio = meio + 1;
aux_vaux = 0;
Enquanto aux_ini <= meio e aux_meio <= fim faça
Se v[aux_ini] < v[aux_meio] então
v_aux[aux_vaux] = v[aux_ini];
aux_ini++;
Senão
v_aux[aux_vaux] = v[aux_meio];
aux_meio++;
Fim Se
aux_vaux++;
Fim Enquanto
Enquanto aux_ini <= meio faça
v_aux[aux_vaux] = v[aux_ini];
aux_vaux++;
aux_ini++;
Fim Enquanto
Enquanto aux_meio <= fim faça
v_aux[aux_vaux] = v[aux_meio];
aux_vaux++;
aux_meio++;
Fim Enquanto
Para aux_vaux de ini a fim faça
v[aux_vaux] = v_aux[aux_vaux - ini];
Fim Para
Fim Merge
Início MergeSort(v[], ini, fim)
Se ini < fim então
meio = (ini + fim)/2;
MergeSort(v[], ini, meio);
MergeSort(v[], meio + 1, fim);
Merge(v[], ini, meio, fim);
Fim Se
Fim MergeSort
Qual a ordem de grandeza no pior caso do algoritmo Merge Sort?
𝑂(𝑛𝑙𝑜𝑔(𝑛)) onde 𝑛 é a quantidade de elementos no vetor.
• WIRTH, Niklaus. Algorithms+ Data Structures= Programs 
Prentice-Hall Series in Automatic Computation. Prentice 
Hall, 1976.
	ESTRUTURA DE DADOS 1 MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MERGE SORT
	MATERIAL UTILIZADO