Algoritmo: Merge Sort

Assim como o Quick Sort, o Merge Sort também utiliza a estratégia dividir para conquistar. Entretanto, a estratégia do Merge Sort é dividir o vetor em vários subvetores já no início e ordenar enquanto reconstrói o vetor. 

Esse método possui duas funções,  a que faz as divisões (neste caso, a função MergeSort()) e a função que a reconstrói (a função Merge()).
A função que faz a divisão, faz de modo recursivo, sempre dividindo o vetor ao meio até que não seja possível dividí-lo. 

Depois de dividido, utiliza-se a função de união que irá pegar os dois vetores e unirá ambos vetores, já ordenando seus elementos. E assim vai reconstruindo até que todos os elementos estejam unidos novamente. Veja o psudocódigo abaixo:



01. Merge(vet:INTEIRO[],inicio:INTEIRO,meio:INTEIRO,fim:INTEIRO)
02. INICIO
03.  var i,z,j,k,aux[vet.tamanho]:INTEIRO
04.  PARA i=inicio ATE fim PASSO 1
05.   aux[i] = vet[i]
06.  FIMPARA
07.  z = inicio
08.  j = meio+1
09.  k = inicio
10.  ENQUANTO (z<=meio E j<=fim) FACA
11.   SE (aux[z] < aux[j]) ENTAO
12.    vet[k] = aux[z]
13.    z++
14.   SENAO
15.    vet[k] = aux[j]
16.    j++
17.   FIMSENAO
18.   k++
19.  FIMENQUANTO
20.  ENQUANTO (z<=meio) FACA
21.   vet[k] = aux[z]
22.   k++
23.   z++
24.  FIMENQUANTO
25. FIM
26.
27. MergeSort(vet:INTEIRO[],inicio:INTEIRO,fim:INTEIRO)
28. INICIO
29.  var meio:INTEIRO
30.  SE (inicio<fim) ENTAO
31.   meio = (inicio+fim) DIV 2  
32.   MergeSort(vet,inicio,meio)
33.   MergeSort(vet,meio+1,fim)
34.   Merge(vet,inicio,meio,fim)
35.  FIMSE
36. FIM
37.
38. Principal():NEUTRO
39. INICIO
40.  var vet = {55, 76, 26, 64, 26, 80, 71, 46}
41.  MergeSort(vet,0,vet.tamanho-1)  
42. FIM
 
 Vamos ver o funcionamento do algoritmo:
Com o vetor que queremos ordenar, primeiro determinamos a posição do meio do vetor:
 
Então dividimos o vetor em duas partes:
Usando apenas a primeira metade do vetor, determina-se o meio e então divide esse subvetor em dois outros vetores (vermelho e laranja):
E fazemos a mesma coisa para o vetor vermelho (formando o vetor amarelo e verde):
 
Tanto o vetor amarelo quanto o vetor verde são unitários, ou seja, possuem apenas um elemento. Então a partir de agora faremos a fusão desses dois vetores. Para isso, contaremos com um vetor auxiliar, que é uma cópia do pedaço original:
 

Agora nós criaremos três variáveis para nos auxiliar a percorrer o vetor: a variável z que irá percorrer a primeira metade do vetor (a parte amarela), a variável j percorrerá a segunda parte do vetor (a parte verde) e a variável k indicará a posição do valor na matriz original:
Com as variáveis posicionadas, vamos começar a ordenar. A comparação consiste em verificar qual dos valores da posição indicada é a menor, se é a z ou a j:
 
Depois de verificado qual deles é o menor, copiamos aquele que for escolhido para a posição k do vetor original:
 
Então, a variável que controla o elemento que foi selecionado e a variável k avançam para a próxima opção:
 
Aqui, a variável z saiu do vetor que ele controla, isso quer dizer que o vetor está ordenado, então podemos concluir a ordenação dessa fase, ou seja, foi feita a fusão entre o vetor amarelo e o verde para formar o vetor vermelho. O motivo de podermos parar quando o z passa da metade é porque significa que no vetor verde não existe um valor que seja menor que os valores do vetor amarelo. Agora que a fusão foi concluída, fazemos os mesmos processos serão feito para o vetor laranja, começando em dividir os vetores:
A fusão com a cópia do pedaço num vetor auxiliar:
As variáveis de controle:
 
A verificação de qual valor é o menor entre a posição z e j e copiando para a posição k o menor deles:

Assim como no caso da fusão amarelo e verde, z e k avançam. A variável z passa da metade, indicando o fim da verificação. Esses dois casos parecem mais simples devido ao fato de ambos subvetores serem pequenos e já estarem ordenados. Agora com isso, o vetor laranja já está ordenado e começaremos a fundir o vetor vermelho com o laranja para formar o azul. Segue o mesmo princípio, a cópia dos valores no vetor auxiliar:
Inicializar as variáveis de controle:
Agora verifica entre as posição z e j qual é o que tem o menor valor e copie para a posição k:
 
Agora, o j vai avançar para a próxima posição assim como o k:
Agora, fazemos novamente a comparação de qual é o menor entre a posição z e a posição j e copiamos para a posição k, aquele que for menor:
Agora, foi o valor z que foi escolhido, por isso a variável z avança, assim como o k:
 
Novamente, copiar o menor valor entre as posições z e j para a posição k:
E tanto os valores de j quanto a de k avançam:
O valor de j passou o vetor, isso significa que todos os números menores foi passado para a primeira metade do vetor. O que precisamos fazer agora é completar o vetor com os valores restante do primeiro vetor, ou seja, copiamos o valor de z atual para a posição k:
Agora tanto k e z passa para a posição adiante. A variável z passa da metade do vetor, ou seja, o processo de fusão está acabado formando o vetor cinza.
Como o vetor cinza já está ordenado, então o algoritmo começará a dividir a segunda metade (o vetor marrom):

E pegando a primeira metade (roxa), dividiremos mais uma vez:
Aqui o processo de fusão segue a mesma coisa do que os dois primeiros, e como os valores já estão ordenados, vamos pular o processo da fusão e partiremos para a divisão da segunda metade:
 
Aqui repete-se o processo de fusão: a cópia para o vetor auxiliar e as variáveis:
E agora pega o menor entre a posição z e j e copie para k:
E k e j avançam.
Como j saiu do vetor, agora resta copiar o restante dos valores de z:
Agora, tanto o z quanto o k avançam uma posição. A variável z saiu da primeira metade, então o processo de fusão entre essas duas partes acabou:
Agora faremos a fusão com o vetor roxo com o azul escuro, novamente copiaremos essa parte do vetor para o vetor auxiliar e setaremos as três variáveis:

Agora começamos a fazer as comparações dos menores:
A variável j saiu do vetor, então resta copiar o restante dos valores do vetor roxo.
E com o z saindo do vetor roxo, finaliza a fusão dos dois vetores formando o vetor marrom.
 
Agora, vamos fazer a última fusão (cinza), juntando a primeira metade do vetor com a segunda metade do vetor (marrom), da mesma forma, começando com o auxiliar e as variáveis:
 
Seguida das comparaçõs dos menores e as cópias:
Como a variável z saiu do vetor cinza, isso indica o fim do processo de fusão. Como esses são os últimos dois pedaços que faltavam ser juntado, então conclui-se a ordenação do vetor.