Mergesort: ordenação por intercalação

Nosso problema:  Rearranjar um vetor v[0 .. n-1] de tal modo que ele fique em ordem crescente, ou seja, de tal modo que tenhamos v[0] ≤ . . . ≤ v[n-1].

Já analisamos alguns algoritmos simples para o problema que consomem tempo proporcional a n².  Vamos examinar agora um algoritmo mais complexo mas mais rápido.

Veja o verbete Merge sort na Wikipedia.

Intercalação (= merge) de vetores ordenados

Antes de resolver nosso problema principal é preciso resolver o seguinte problema auxiliar:  dados vetores crescentes v[p .. q-1] e v[q .. r-1], rearranjar v[p .. r-1] em ordem crescente.  Basta tratar do caso em que os vetores v[p .. q-1] e v[q .. r-1] não são vazios.

p						q-1	q			r-1
111	333	555	555	777	999	999	222	444	777	888

É fácil resolver o problema em tempo proporcional ao quadrado de r-p:  basta ordenar o vetor v[p..r-1] sem dar atenção ao estado ordenado das duas "metades". Mas isso é muito lento; precisamos de um algoritmo mais rápido.

O problema é fácil, mas não é trivial. Será preciso usar um vetor auxiliar, digamos  w,  do mesmo tipo e mesmo tamanho que v[p..r-1]. 

// A função recebe vetores crescentes v[p..q-1] e 
// v[q..r-1] e rearranja v[p..r-1] em ordem crescente.

void 
intercala1 (int p, int q, int r, int v[]) 
{
   int i, j, k, *w;
   w = mallocX ((r-p) * sizeof (int));
   i = p; j = q;
   k = 0;

   while (i < q && j < r) {
      if (v[i] <= v[j])  w[k++] = v[i++];
      else  w[k++] = v[j++];
   }
   while (i < q)  w[k++] = v[i++];
   while (j < r)  w[k++] = v[j++];
   for (i = p; i < r; ++i)  v[i] = w[i-p];
   free (w);
}

Desempenho da intercalação

O tempo que a função consome para fazer o serviço é proporcional ao número de comparações entre elementos do vetor. Esse número é no máximo   r - p - 1 .   O consumo de tempo também é proporcional ao número de movimentações, ou seja, cópias de elementos do vetor de um lugar para outro. Esse número é igual a  2(r-p).   Resumindo, o consumo de tempo da função é proporcional ao número de elementos do vetor, ou seja,

proporcional  a   r - p .

Exercícios

Intercalação com sentinelas

Sedgewick tem uma maneira mais elegante de escrever o algoritmo de intercalação.  O primeiro for copia v[p..q-1] para w[0..q-p-1];  o segundo, copia v[q..r-1] para w[q-p..r-p-1] em ordem invertida. Com isso, a intercalação de w[0..q-p-1] com w[q-p..r-p-1] pode ser feita em um único for.

// A função recebe vetores crescentes v[p..q-1] e 
// v[q..r-1] e rearranja v[p..r-1] em ordem crescente.

void
intercala2 (int p, int q, int r, int v[])
{
   int i, j, k, *w;
   w = mallocX ((r-p) * sizeof (int));

   for (i = 0, k = p; k < q; ++i, ++k) w[i] = v[k];
   for (j = r-p-1, k = q; k < r; --j, ++k) w[j] = v[k];
   i = 0; j = r-p-1;
   for (k = p; k < r; ++k)
      if (w[i] <= w[j]) v[k] = w[i++];
      else v[k] = w[j--];
   free (w);
}

Tal como a versão anterior, esta consome tempo proporcional a  r - p.

Exercícios

Mergesort

Agora podemos usar qualquer das funções intercala discutidas acima para escrever um algoritmo rápido de ordenação: o algoritmo recebe um vetor v[p..r-1] e rearranja o vetor em ordem crescente. O algoritmo é recursivo. A base da recursão é o caso p ≥ r-1; nesse caso não é preciso fazer nada.

// A função mergesort rearranja o vetor v[p..r-1]
// em ordem crescente.

void
mergesort (int p, int r, int v[])
{
   if (p < r-1) {
      int q = (p + r)/2;
      mergesort (p, q, v);
      mergesort (q, r, v);
      intercala (p, q, r, v);
   }
}

O resultado da divisão por 2 na expressão (p+r)/2 é automaticamente truncado. Por exemplo, (3+6)/2 vale 4.  Para rearranjar v[0..n-1] em ordem crescente basta executar mergesort (0, n, v).

0	1	2	3	4	5	6	7	8	9	10
111	999	222	999	333	888	444	777	555	666	555
111	999	222	999	333	888	444	777	555	666	555
111	999	222	999	333	888	444	777	555	666	555
:
:
111	999	222	333	999	444	777	888	555	555	666
111	222	333	999	999	444	555	555	666	777	888
111	222	333	444	555	555	666	777	888	999	999

Exercícios

Mergesort: desempenho do algoritmo

Quanto tempo o algoritmo consome para ordenar v[0..n-1]?  Como o número de elementos do vetor é reduzido à metade em cada chamada do mergesort, o número total de "rodadas" é log₂n. Na primeira rodada, nosso problema original é reduzido a dois outros:  ordenar  v[0 .. n/2-1]  e ordenar  v[n/2 .. n-1]. Na segunda rodada temos quatro problemas: ordenar v[0..n/4-1], v[n/4..n/2-1], v[n/2..3n/4-1] e v[3n/4..n-1]. E assim por diante. O tempo total que intercala gasta em cada "rodada" é n  (por quê? pense!). Conclusão: mergesort consome tempo proporcional a

n log₂n .

Isso é bem melhor que o tempo n² gasto pelos algoritmos da página anterior. Por exemplo, se a ordenação de n números exige  t  segundos, a ordenação de  16n  números exigirá menos que  26t  segundos (supondo n ≥ 100) contra os  256t  segundos do algoritmo anterior.

Observação final: Como mergesort é mais complexo que os algoritmos da página anterior, ele só é realmente mais rápido na prática quando n é suficientemente grande.

Mergesort: animações

Veja algumas animações do algoritmo Mergesort:

• Sorting Algorithms Animation by David R. Martin
• Animação de R. Sedgewick (Universidade de Princeton)
• MergeSort demo, preparada por David Neto na Universidade de Toronto em 1996.
• Sorting Algorithms, página de Pat Morin na Universidade de Carlton, Canadá
• Sorting Algorithms na Universidade de British Columbia
• Merge-sort with Transylvanian-saxon (German) folk dance, created at Sapientia University (Romania)

Exercícios

Versão iterativa do Mergesort

A versão iterativa do algoritmo Mergesort recebe um vetor v[0..n-1] e rearranja o vetor em ordem crescente. A ideia é muito simples: a cada iteração, intercalamos dois "blocos" com  b  elementos cada: o primeiro bloco com o segundo, o terceiro com o quarto etc.  A variável b assume os valores 1, 2, 4, . . . .

// Esta função rearranja o vetor v[0..n-1] 
// em ordem crescente.

void
mergesort_i (int n, int v[])
{
   int p, r;
   int b = 1;
   while (b < n) {
      p = 0;
      while (p + b < n) {
         r = p + 2*b;
         if (r > n) r = n;
         intercala (p, p+b, r, v);
         p = p + 2*b; 
      }
      b = 2*b;
   }
}

A figura ilustra a iteração b == 2.

0				p		p+b		p+2*b		n-1
111	999	222	999	333	888	444	777	555	666	555

Exercícios

Mais exercícios