MergeSort Dividir Conquistar

Análise do algoritmo Mergesort

Esta página é inspirada na segunda parte do capítulo 2 do CLRS. Ela trata do seguinte problema de ordenação:

Problema da ordenação: Rearranjar um vetor A[p..r] de modo que ele fique em ordem crescente.

Veja o verbete Merge sort na Wikipedia.

Ordenação por intercalação

Podemos usar a estratégia da divisão e conquista para resolver o problema. O algoritmo resultante supõe que p ≤ r e adota o caso p = r como base da recursão:

Mergesort (A, p, r)
1 se p < r então
2 q ← ⌊(p+r)/2⌋
3 Mergesort (A, p, q)
4 Mergesort (A, q+1, r)
5 Intercala (A, p, q, r)
(Veja definição de piso.) Observe que p ≤ q < r. Com isso, tanto A[p .. q] quanto A[q+1 .. r] são estritamente menores que A[p .. r]. Isso garante que a execução do algoritmo termina (mais cedo ou mais tarde).

p q q+1 r
111 333 555 555 777 999 999 222 444 666 888
O que faz o algoritmo Intercala? O algoritmo recebe vetores crescentes A[p .. q] e A[q+1 .. r] e rearranja o vetor A[p .. q .. r] de modo que ele fique crescente. Para resolver esse problema, eu poderia ignorar o caráter ordenado dos dois subvetores e usar o algoritmo de inserção. Mas é possível fazer algo mais eficiente (desde que tenhamos permissão para usar um vetor auxiliar B[p..r]):

Intercala (A, p, q, r)
6 para i crescendo de p até q faça
7 B[i] ← A[i]
8 para j crescendo de q+1 até r faça
9 B[r+q+1−j] ← A[j]
10 i ← p
11 j ← r
12 para k crescendo de p até r faça
13 se B[i] ≤ B[j]
14 então A[k] ← B[i]
15 i ← i+1
16 senão A[k] ← B[j]
17 j ← j−1
(Esta versão do algoritmo é do Algorithms in C de Sedgewick.) Suponha que cada execução de cada linha do código consome 1 unidade de tempo. Então a execução de Intercala consome 6n+5 unidades de tempo, onde n é o número de elementos do vetor