Algoritmo de Ordenação: Merge Sort

A idéia básica do Merge Sort é criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, o algoritmo Merge Sort divide a sequência original em pares de dados, agrupa estes pares na ordem desejada; depois as agrupa as sequências de pares já ordenados, formando uma nova sequência ordenada de quatro elementos, e assim por diante, até ter toda a sequência ordenada.


Algoritmo:

Os três passos úteis dos algoritmos dividir-para-conquistar, que se aplicam ao Merge Sort são:

1. Dividir: Dividir os dados em subsequências pequenas;
   Este passo é realizado recursivamente, iniciando com a divisão do vetor de n elementos em duas metades, cada uma das metades é novamente dividida em duas novas metades e assim por diante, até que não seja mais possível a divisão (ou seja, sobrem n vetores com um elemento cada).
2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
3. Combinar: Juntar as duas metades em um único conjunto já classificado.
Para completar a ordenação do vetor original de n elementos, faz-se o merge ou a fusão dos sub-vetores já ordenados.

A desvantagem do Merge Sort é que requer o dobro de memória, ou seja, precisa de um vetor com as mesmas dimensões do vetor que está sendo classificado.

Observe a figura: Vetor original com elemento desordenados.

0	1	2	3	4	5	6	7	8
53	25	46	32	23	37	41	17	10

O vetor original é subdividido em dois vetores.

0	1	2	3	4	5	6	7	8
53	25	46	32	23	37	41	17	10

Cada um dos subvetores é novamente dividido. 

0	1	2	3	4	5	6	7	8
53	25	46	32	23	37	41	17	10

E assim por diante. 

0	1	2	3	4	5	6	7	8
53	25	46	32	23	37	41	17	10
53	25	46	32	23	37	41	17	10

Após todo o processo de divisão, ocorre o processo da fusão ordenada dos subvetores. O subvetor (53) com o subvetor (25). Ordenando os dois.

0	1	2	3	4	5	6	7	8
25	53	46	32	23	37	41	17	10

O subvetor (25, 53) com o subvetor (46). Ordenando os dois.

0	1	2	3	4	5	6	7	8
25	46	53	32	23	37	41	17	10

O subvetor (32) com o subvetor (23).

0	1	2	3	4	5	6	7	8
25	46	53	23	32	37	41	17	10

O subvetor (25,46,53) com o subvetor (23,32). Ordenando os dois.

0	1	2	3	4	5	6	7	8
23	25	32	46	53	37	41	17	10

O mesmo processo se repete no subvetor (37, 41, 17, 10).

0	1	2	3	4	5	6	7	8
23	25	32	46	53	37	41	17	10
23	25	32	46	53	37	41	10	17
23	25	32	46	53	10	17	37	41

Os subvetores resultantes (23,25, 32, 36,53) e (10, 17, 37, 41) são fundidos ordenandos durante a fusão.

0	1	2	3	4	5	6	7	8
10	17	23	25	32	37	41	46	53

O processo de ordenação termina!


Observe este video, um exemplo prático do MergeSort:





Veja também um exemplo de algoritmo genérico MergeSort em linguagem C++:

Algoritimo (fonte wikipedia)

 Bons Estudos!!

Fonte (cos.ufrj.br)