Mergesort
Katia Guimarães
Problema de Ordenação
Dado um array com n números naturais,
ordenar estes números em ordem
crescente.
INPUT:
95
48
70
86
21
37
OUTPUT: 21
37
48
70
86
95
2
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.
3
Exemplo de Mergesort
INPUT:
47 26 33 05 99 38 64 15
1. Divide: 47 26 33 05
99 38 64 15
2. Resolve Recursivamente:
a) Primeira metade 47 26 33 05
(Divide, Resolve recursivamente, Intercala
Obtendo 05 26 33 47 )
b) Segunda metade 99 38 64 15
(Divide, Resolve recursivamente, Intercala
Obtendo 15 38 64 99 )
4
Exemplo de Mergesort
INPUT:
47 26 33 05 99 38 64 15
2. Resolve Recursivamente:
a) (Retorna 05 26 33 47 )
b) (Retorna 15 38 64 99 )
3. Intercala as soluções parciais:
05 15 26 33 38 47 64 99
5
Algoritmo Mergesort
Entrada : (A, B, ini, fim)
Saída
: B [ ini .. fim], array A ordenado de ini até fim
begin
if (fim = ini)
retorne(*);
else
MergeSort (A, B, ini, (ini + fim)/2 );
MergeSort (A, B, (ini + fim)/2 +1, fim);
Intercala (A, B, ini, (fim+ini)/2 +1, (fim-ini+1) );
retorne(*);
end
(*) O array com a resposta depende do tamanho de A.
6
Algoritmo Intercala
Entrada: (A, B, ini1, ini2, n)
Saída: Elementos B[ini1 .. ini1+n-1] ordenados
begin
int i  ini1, j  ini2, k  ini1;
while ( i < ini2 and j < ini1+n ) do
if (A[i]  A[j] )
then { B[k]  A[i]; i  i+1; k  k+1 }
else { B[k]  A[j]; j  j+1; k  k+1 }
while ( i < ini2 ) do
/*copia 1a. metade.*/
{ B[k]  A[i]; k  k+1; i  i+1 }
while ( j < ini1+n ) do /*copia 2a. metade.*/
{ B[k]  A[j]; k  k+1; j  j+1 }
return ( B )
end
7
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
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
8
Implementação do Mergesort
O procedimento Intercala requer o uso de um
segundo array, B, para receber os dados ordenados.
Note que no retorno de Mergesort com um array de
tamanho 1, a resposta encontra-se no array A (o
array original de entrada). No próximo nível (array
de comprimento 2) o resultado da intercalação
estará no array B.
Podemos administrar este problema de duas
maneiras.
9
Implementação do Mergesort
Podemos administrar este problema de
duas maneiras:
- Copiando a porção do array referente ao
resultado de volta para o array A, ou
- Utilizando uma chave para indicar a “direção”
dos movimentos de Intercala.
10
Complexidade do Mergesort
TMergesort(n) =
2 • TMergesort(n/2) + cte • n + cte
Forma Fechada de Recorrência
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
11
Complexidade do Mergesort
Temos que TMS(n) = 2i • TMS(n/2i) + i • c • n + (2i-1) • c.
Note que sabemos o valor de TMS(1).
Para obter um valor fechado, queremos que (n/2i) = 1.
Isso ocorre quando i = log2n.
TMS(n) = 2log2n • cte + (log2n) • c • n + (2log2n - 1) • c
= n • cte + c • n • log2n + c •(n-1)
= c • nlog2n + (cte+c) • n - c
TMS(n) = O(n • log2n)
12