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](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjrQ17ioPD1QUDpTaMeCnKyHfPrBwdQN4_L6h8UH2Bp3f90mVhyphenhypheniCpB0QuejaMiENqffhQMc7-uRFvP-qEx7ucPFkxOtenfHiwwvRQjmQI5qlmtgGlKlUdXDGMIE41484zrTMxFHxqRuxlc/s1600/merge-sort.jpg)
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.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUbLqklOXGmHw20fOTYt9n7u_GMjcQAXtlkCD08QMSokKN3enBb14Hq4eHa_Nf0kXtpcsj8e8ulaIXOAvtZOSEd_bBXee3JInESmnVlYjN7i536NLcX4vZZ4PeL3mdMw8pv341qXNviELP/s1600/merge-sort-vetor-01.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjPnZ2uIrok7aXdzt98ijfs4djQwDWnE5kBCX7mWlnHpiTBn56AHW9sdlh5MCxGufYeq10a3kn_efWDsv_wadrTKyu9wghc0eAp2-K8Ay7kAb07LzIDktotFJKBa81Kc1KHxxjqAwVtyc_q/s1600/merge-sort-vetor-02.png)
Reaplicamos o método aos dois subvetores
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLLEbNRAcfKqrMeyLne1AKrOCxdwVyekYePc6R6N0FMF6uzOsZplEjoDc1yHFrlJbPSvcUxu89youyKon178G47Zz1OJ58MpC_y2R52snZ0KxesCALxjEhyphenhyphenTLZVpVCSOCLgQ-tQzpPvmIc/s1600/merge-sort-vetor-03.png)
De novo,
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXz4PnXIV8SNkeJ81DkttdcX2X_bKgPPD9P_j_WKS8lSV3b3kXferYXB-rLFGOcQGOar1WRz9w67NjNooJLPQHWtuJmdVLFoeChBLgXa71ZQ6rOjV1_oFRFe1euNKjuRVbGYla-r74iD2z/s1600/merge-sort-vetor-04.png)
Mais uma vez, pois ainda não alcançamos o caso base em alguns subvetores
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuP5DDckSEGMgNV3jWf7XgAhGwVn2zoN2Z6-jiJzaK_ZZzgTFQBupQwkFIGof2T3n-zqvW5oCL0tYjjtq0vh6aTryiihBeVOQxXx8fU3Ve2kuxzJGsDzqgWnpm6TOmnMMmSM1xTLkuwLKK/s1600/merge-sort-vetor-05.png)
Finalmente, fazemos a fusão dos subvetores
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPPlrIGRdehPyfeyxqdiI6BrhY5TN6BHgly-be4HpUbzGePnO0TPFxlQbzYTa9yzdY9Cm_JBLszxZCqjfFXVCc9l9LZ-DOD38lMuUu5fnop6gjNhmW5f3c8DaxsoC-ODaWgyU8_NinmV2_/s1600/merge-sort-vetor-06.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMDmdCOt4RaXvfDdbKM6IAtIfz400AwE0e-IIlKeKLQpmwQ-IgzmYhc1rwaNGegZmhzpQPLqCdv7CFO8nbXd3IKsaEtTTnzzle60OA_XHVc2TO-v0UOw8uIrS-SbxrfLKgb6AQgkDCETnE/s1600/merge-sort-vetor-07.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhpfgRqiQABYTDooz3MWQ5mHB-Cr5oIAPrObuE3ehScGPG1MZY5HSNWZ8dsfZQ-1Gsx0SKzviwjVru1XQSfINOy9fBCp-h-ZVTbQNLDnKS8N1xL_k5Gsll0bH2K9KMnpAzIfWnwQp7VZc5S/s1600/merge-sort-vetor-08.png)
O diagrama a seguir ilustra todas as etapas
![Diagrama com todas as etapas do Merge Sort para ordenar um vetor](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUQ1lOw8KLNu-k4u_uzaOs_gvSgPQf32YHk0TS5iA77U8A1NAPVwUkb2rNlDE34lLNRMF94f2mnkhNNXZodu5dwgpjZZHs83o6ryNTFi1P0lxmTz9Clu9dUdtV9RbW15XOdY_ixwXdCaaL/s640/diagrama-merge-sort.png)
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.
Merge Sort em pseudocódigo
Como vimos, o Merge Sort possui duas etapas
- divisão do vetor em subvetores até atingirmos o caso base;
- 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.
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.
Códigos
Os códigos em Java, C e em JavaScript do Merge Sort podem ser obtidos nos links a seguir
Referências
- [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
Nenhum comentário:
Postar um comentário