O mergesort é um algoritmo de ordenação do tipo dividir-para-conquistar. Sua ideia básica consiste em dividir o problema em vários subproblemas, e resolver esses subproblemas por meio da recursividade e, em seguida,após todos os subproblemas terem sido resolvidos,ocorre a conquista, que é a união das resoluções dos subproblemas.O algoritmo mergesort, apresentado em seguida, está codificado em C/C++.Esse algoritmo ordena o vetor de inteiros a[p],..., a[r](onde, p<r) usando um vetor auxiliar b[p],..., b[r]. O vetor a[ ] é dividido recursivamente ao meio em duas instâncias menores, que são ordenadas e então colocadas juntas, ordenando todo o vetor. No código estão faltando as linhas que fazem a divisão por recursão (linhas 7 e 8) e as linhas que concretizam a fase de conquista, unindo todas as intercalações no vetor principal (linhas 11 e 12).
- void mergesort(int a[], int p, int r)
- {
- int i,j,k,m;
- if (r > p)
- {
- m = (r + p)/2;
- ...
- ...
- for (i = m+1; i> p; i--) b[i-1] = a[i-1];
- for (j = m; j < r; j++) b[r+m-j] = a[j+1];
- ...
- ...
- }
- }
As linhas 7,8, 11 e 12, que complementam o código do mergesort de maneira CORRETA, são:
7. mergesort(a, p, m);
8. mergesort(a, m+1, r);
…
11. for (k = p; k <= r; k++)
12. a[k] = (b[i]<b[j]) ? b[i++] : b[j--];
7. mergesort(a, p, m+1);
8. sort(a, m+1, r);
...
11. for (k = m; k <= r; k--)
12. a[k] = (b[i]<b[j]) ? b[i++] : b[j--];
7. mergesort(a, p, m);
8. mergesort(a, m+1, r);
…
11. for (k = m; k <= m; k++)
12. a[m] = (b[m]<b[j]) ? b[m++] : b[m--];
7. sort(a, p, m);
8. sort(a, m+1, r);
...
11. for (k = p; k <= r; k++)
12. a[k] = (b[i]<b[j]) ? b[i++] : b[j--];
7. sort(a, p, m);
8. merge(a, m+1, r);
...
11. for (k = p; k <= r; k++)
12. a[k] = (b[i]<b[j]) ? b[i++] : b[j--];