Merge Sort

Por
| 

O Merge Sort (ordenação por intercalação/fusão) é um algoritmo de ordenação recursivo cujo mérito pela criação é atribuído ao físico e matemático John von Neumann.

Algoritmo de ordenação por intercalação Merge Sort

A complexidade no tempo desse algoritmo de divisão e conquista é $O(n\log n)$, sendo mais eficiente do que os algoritmos Bubble Sort, Selection Sort e Insertion Sort, que já foram analisados em artigos anteriores do blog.

Neste artigo, será realizada uma análise do Merge Sort. Como é de costume, também disponibilizarei o algoritmo codificado em Java, C e em JavaScript.

Índice

Como funciona o Merge Sort?

A ideia do Merge Sort é dividir o vetor em dois subvetores, cada um com metade dos elementos do vetor original. Esse procedimento é então reaplicado aos dois subvetores recursivamente.

Quando os subvetores têm apenas um elemento (caso base), a recursão para. Então, os subvetores ordenados são fundidos (ou intercalados) num único vetor ordenado.

Como exemplo, ordenaremos o vetor [5, 2, 7, 6, 2, 1, 0, 3, 9, 4]. Inicialmente, dividimos o vetor em dois subvetores, cada um com metade dos elementos do vetor original.

Reaplicamos o método aos dois subvetores

De novo,

Mais uma vez, pois ainda não alcançamos o caso base em alguns subvetores

Finalmente, fazemos a fusão dos subvetores

O diagrama a seguir ilustra todas as etapas

Diagrama com todas as etapas do Merge Sort para ordenar um vetor
Diagrama com todas as etapas do Merge Sort para ordenar um vetor (ampliar)

No exemplo, várias etapas foram realizadas simultaneamente para não estender o artigo. Entretanto, na realidade, o Merge Sort ordena os subvetores um por vez.

Podemos realizar algumas etapas paralelamente se tivermos à nossa disposição um processador com mais de um núcleo. Para isso, o Merge Sort precisa ser codificado para que possa utilizar múltiplas threads.

Ir para o índice

Merge Sort em pseudocódigo

Como vimos, o Merge Sort possui duas etapas

  1. divisão do vetor em subvetores até atingirmos o caso base;
  2. fusão dos subvetores (merge).

A primeira etapa consiste no seguinte algoritmo

01. mergesort(A[0...n - 1], inicio, fim)
02. |   se(inicio < fim)
03. |   |   meio ← (inicio + fim) / 2 //calcula o meio
04. |   |   mergesort(A, inicio, meio) //ordena o subvetor esquerdo
05. |   |   mergesort(A, meio + 1, fim) //ordena o subvetor direito
06. |   |   merge(A, inicio, meio, fim) //funde os subvetores esquerdo e direito
07. |   fim_se
08. fim_mergesort

A etapa de fusão é [1]

01. merge(A[0...n - 1], inicio, meio, fim)
02. |   tamEsq ← meio - inicio + 1 //tamanho do subvetor esquerdo
03. |   tamDir ← fim - meio //tamanho do subvetor direito
04. |   inicializar vetor Esq[0...tamEsq - 1]
05. |   inicializar vetor Dir[0...tamDir - 1]
06. |   para i ← 0 até tamEsq - 1
07. |   |   Esq[i] ← A[inicio + i] //elementos do subvetor esquerdo
08. |   fim_para
09. |   para j ← 0 até tamDir - 1
10. |   |   Dir[j] ← A[meio + 1 + j] //elementos do subvetor direito
11. |   fim_para
12. |   idxEsq ← 0 //índice do subvetor auxiliar esquerdo
13. |   idxDir ← 0 //índice do subvetor auxiliar direito
14. |   para k ← inicio até fim
15. |   |   se(idxEsq < tamEsq)
16. |   |   |   se(idxDir < tamDir)
17. |   |   |   |   se(Esq[idxEsq] < Dir[idxDir])
18. |   |   |   |   |   A[k] ← Esq[idxEsq]
19. |   |   |   |   |   idxEsq ← idxEsq + 1
20. |   |   |   |   senão
21. |   |   |   |   |   A[k] ← Dir[idxDir]
22. |   |   |   |   |   idxDir ← idxDir + 1
23. |   |   |   |   fim_se
24. |   |   |   senão
25. |   |   |   |   A[k] ← Esq[idxEsq]
26. |   |   |   |   idxEsq ← idxEsq + 1
27. |   |   |   fim_se
28. |   |   senão
29. |   |   |   A[k] ← Dir[idxDir]
30. |   |   |   idxDir ← idxDir + 1
31. |   |   fim_se
32. |   fim_para
33. fim_merge

Observe que o método merge utiliza dois vetores auxiliares. A utilização desses vetores faz com o Merge Sort tenha complexidade $O(n)$ no espaço.

Por causa da cópia de elementos entre os vetores auxiliares e o vetor A, a complexidade no tempo do método merge é $\Theta(n)$ ou $O(n)$.

Alternativamente, podemos utilizar um único vetor auxiliar na ordenação, porém a complexidade no tempo e no espaço será a mesma.

Ir para o índice

Complexidade assintótica

A equação de recorrência do Merge Sort é [1]

$$T(n)=2T(n/2)+\Theta(n)$$

O termo $2T(n/2)$ é o tempo para ordenar dois vetores de tamanho $n/2$, já o termo $\Theta(n)$ é o tempo para fundir/intercalar esses vetores, isto é, é o tempo do método merge.

A equação de recorrência anterior já foi resolvida algumas vezes em postagens anteriores do blog, porém resolveremos de novo.

Podemos utilizar o método de Akra-Bazzi ou o método mestre na resolução. Optaremos pelo segundo.

De acordo com o teorema mestre, temos

$$a=2,\quad b=2,\quad f(n)=\Theta(n)$$

Além disso,

$$\log_b a=\log_2 2=1$$

Como $f(n)=\Theta\left(n^{\log_b a}\right)=\Theta(n)$, então a equação de recorrência satisfaz o segundo caso do teorema mestre, portanto

$$T(n)=\Theta\left(n^{\log_b a}\log n\right)=\Theta(n\log n)$$

Ou, equivalentemente, $T(n)=O(n\log n)$. Essa complexidade é a mesma no melhor caso, no caso médio e no pior caso.

Se quiser saber como resolver a equação de recorrência do Merge Sort através do método de Akra-Bazzi, acesse postagem: O Método de Akra-Bazzi na Resolução de Equações de Recorrência.

Ir para o índice

Códigos

Os códigos em Java, C e em JavaScript do Merge Sort podem ser obtidos nos links a seguir

Ir para o índice

Referências

Siga o blog

Redes sociais: Facebook, Twitter, Google+, YouTube, Pinterest, Instagram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário