MergeSort
Intercalação
David Menotti
Estruturas de Dados I
DECOM – UFOP
Problema de Ordenação

Dado um arranjo com n números naturais,
ordenar estes números em ordem crescente.
Entrada: 95
48
70
86
21
37
Saída:
37
48
70
86
95
© David Menotti
21
Estrutura de Dados I
Abordagem Dividir-para-Conquistar

Método em Computação que consiste em



Dividir a entrada em conjuntos menores
Resolver cada instância menor de maneira
recursiva
Reunir as soluções parciais para compor a
solução do problema original.
© David Menotti
Estrutura de Dados I
Abordagem Balanceamento

Métodos de ordenação de divisão por
conquista



SelectSort
QuickSort (pior caso?)
Divisão do problema de forma balanceada
MergeSort
© David Menotti
Estrutura de Dados I
Exemplo de MergeSort
Entrada:
47 26 33 05
99 38 64 15
1.
Divide: 47 26 33 05
99 38 64 15
2.
Resolve Recursivamente:
1.
Primeira metade
47 26 33 05
(Divide, Resolve recursivamente, Intercala
Obtendo 05 26 33 47 )
2.
Segunda metade
99 38 64 15
(Divide, Resolve recursivamente, Intercala
Obtendo 15 38 64 99 )
© David Menotti
Estrutura de Dados I
Exemplo de MergeSort
Entrada:
99 38 64 15
Resolve Recursivamente:
2.
(Retorna 05 26 33 47 )
(Retorna 15 38 64 99 )
1.
2.
2.
47 26 33 05
Intercala as soluções parciais:
05 15 26 33
38 47 64 99
© David Menotti
Estrutura de Dados I
Algoritmo MergeSort
void MergeSort(Item* A,int ini,int fim)
{
int meio;
if (fim == ini)
return;
else
{
meio = ( ini + fim ) / 2;
MergeSort(A, ini, meio );
MergeSort(A, meio+1, fim);
Intercala(A, ini, meio, fim );
return;
}
}
© David Menotti
Estrutura de Dados I
Implementação de Intercala
IntercalaAB(Item* c,Item* a,int N,Item* b,int M)
{
int i, j, k;
for (i = 0, j = 0, k = 0; k < N+M; k++)
{
if ( i == N ) { c[k] = b[j++]; continue; }
if ( j == M ) { c[k] = a[i++]; continue; }
if ( a[i] < b[j] )
c[k] = a[i++];
else
c[k] = b[j++];
}
}
© David Menotti
Estrutura de Dados I
Exemplo de MergeSort
6
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
2
6
6
5
5
5
5
2
2
2
2
2
2
2
2
2
© David Menotti
8
8
5
6
6
6
6
5
5
5
5
5
5
5
5
3
5
5
8
8
8
8
8
6
6
6
6
6
6
6
6
4
10 9 12 1
10 9 12 1
10 9 12 1
10 9 12 1
9 10 12 1
9 10 1 12
1
9 10 12
8
9 10 12
8
9 10 12
8
9 10 12
8
9 10 12
8
9 10 12
8
9 10 12
8
9 10 12
8
9 10 12
5
6
7
8
15 7
3 13 4 11
15 7
3 13 4 11
15 7
3 13 4 11
15 7
3 13 4 11
15 7
3 13 4 11
15 7
3 13 4 11
15 7
3 13 4 11
15 7
3 13 4 11
7 15 3 13 4 11
7 15 3 13 4 11
3
7 13 15 4 11
3
7 13 15 4 11
3
7 13 15 4 11
3
7 13 15 4 11
3
4
7 11 13 14
9 10 11 12 13 14
16
16
16
16
16
16
16
16
16
16
16
16
14
14
15
15
14
14
14
14
14
14
14
14
14
14
14
14
16
16
16
16
Estrutura de Dados I
Implementação do MergeSort




O procedimento Intercala requer o uso de um
segundo arranjo, B, para receber os dados
ordenados.
Note que no retorno de Mergesort com um arranjo
de tamanho 1, a resposta encontra-se no arranjo A
(o arranjo original de entrada).
No próximo nível (arranjo de comprimento 2) o
resultado da intercalação estará no arranjo B.
Podemos administrar este problema de duas
maneiras.
© David Menotti
Estrutura de Dados I
Implementação do MergeSort

Podemos administrar este problema de duas
maneiras:


Copiando a porção do arranjo referente ao
resultado de volta para o arranjo A, ou
Utilizando uma chave para indicar a “direção”
dos movimentos de Intercala.
© David Menotti
Estrutura de Dados I
Complexidade do MergeSort
TMergeSt(n) =
2 TMergesort(n/2) + cte n + cte
Desenvolvendo
TMS (n) = 2 TMS(n/2) + c n + c
= 2 [ 2 TMS(n/4) + c n/2 + c ] + c n + c
= 4 TMS(n/4) + 2c n + 3c
= 4 [ 2 TMS(n/8) + c n/4 + c ] + 2c n + 3c
= 8 TMS(n/8) + 3c n + 7c
= ...
TMS (n) = 2i TMS(n/2i) + i c n + (2i-1) c
© David Menotti
Estrutura de Dados I
Complexidade do MergeSort

Temos que TMS(n) = 2i TMS(n/2i) + i c n + (2i-1) c.

Tem-se que TMS(1) = 1 e (n/2i) = 1  (i = log2n).
TMS(n) = 2log2n cte + (log2n) c n + (2log2n - 1) c
= n cte + c n log2n + c (n-1)
= c n log2n + (cte+c) n - c
TMS(n) = O(n log2n)
© David Menotti
Estrutura de Dados I
MergeSort

Vantagens



Como HeapSort, MergeSort é O(n log n)
Indicado para aplicações que exigem restrição de
tempo (executa sempre em um determinado
tempo para um dado n)
Passível de ser transformado em estável



Implementação de intercala
Fácil Implementação
Desvantagens


Utiliza memória auxiliar – O(n)
Na prática mais lento que HeapSort
© David Menotti
Estrutura de Dados I