Merge Sort

mergesort.alg

Procedimento dividir(inici, fim: inteiro )
var
   meio:inteiro
inicio
   // dividir
   se (inici <  fim) entao

      // identifica o meio (divisão resultado inteiro)
      meio   := (inici + fim) DIV 2
      
      // recursividades -----

      // 1. dividir esquerda
      dividir (inici, meio)

      // 2. dividir dierita
      dividir (meio+1, fim)
      
      // 3. juntar de forma ordenada
      mesclar (inici, meio, fim)
      
   fimse
fimprocedimento


procedimento mesclar (inici, meio, fim: inteiro )
var
   i_esquerda:  inteiro // índice da lista da querda
   i_direita:   inteiro // índice da lista da direita
   i_aux:       inteiro // posição a preencher na lista_B
   i_sobra:     inteiro // posição na loop da sobra
   i_reposicao: inteiro // posição para atualizar lista_A
   
   lista_B:     vetor [1..7] de inteiro // lista auxiliar
inicio

   i_esquerda := inici;    // primeiro índice da esquerda
   i_direita  := meio + 1; // primeiro índice da direita
   
   i_aux      := inici;

   // enquanto tem itens na esquerda E na direita
   enquanto (i_esquerda <= meio) e (i_direita <= fim) faca

      // INFO: compara um item da esquerda com um item da direita
      
      // Se o item da ESQUERDA for menor
      se lista_A[i_esquerda] <= lista_A[i_direita] entao
      
         lista_B[i_aux]      := lista_A[i_esquerda]; // preenche lista B
         i_esquerda          := i_esquerda + 1;      // aumenta índice da esquerda (pra usar na próxima comparação)

      // se o item da DIREITA for menor
      senao
      
         lista_B[i_aux]      := lista_A[i_direita];
         i_direita           := i_direita + 1;
         
      fimse
      
      // pronto, já preenchemos um item na lista_B (linha 50 ou 57),
      // então vamos para o próximo
      i_aux := i_aux + 1;
      
   fimenquanto

   // Este bloco abaixo resolve o seguinte problema.
   // imagina que após a repetição do bloco acima, o resultao final foi:
   // [] e [22, 33, 66] -> sobrou item na direita
   // significa que após fazer as comparações, sobrou uma lista
   // (da direita ou esquerda) com uma sobra
   
   // se o índice da esquerda for maior que o meio,
   // quer dizer que a lista da esquerda está vazia, tem sobra na direita
   se i_esquerda > meio entao
   
      // preenche sobra da direita na lista_B (aqui já está ordenado)
      Para i_sobra de i_direita ate fim faca
         lista_B[i_aux] := lista_A[i_sobra];
         i_aux          := i_aux + 1;
      fimpara
      
   // neste caso abaixo é por que a sobra está na esquerda
   senao
   
      // preenche sobra da esquerda na lista_B
      Para i_sobra de i_esquerda ate meio faca
         lista_B[i_aux] := lista_A[i_sobra];
         i_aux          := i_aux + 1;
      fimpara
   fimse

   // Atualiza lista_A com os itens já ordenados da lista_B
   para i_reposicao de inici ate fim faca
      lista_A[i_reposicao]   :=  lista_B[i_reposicao];
   fimpara
fimprocedimento


Algoritmo "testa-mergesort"

var
   lista_A: vetor [1..7] de inteiro
   x,inici,fim:inteiro

inicio

   // define dados aleatórios para o próximo comando "leia"
   aleatorio 0,99

   // preencher a lista_A
   para x de 1 ate 7 faca
      leia (lista_A[x])
   fimpara

   inici   := 1
   fim     := 7
   
   dividir(inici, fim)

   // Escreve o resultado já ordenado
   para x de 1 ate 7 faca
      escreva (lista_A[x])
   fimpara
   
fimalgoritmo