Mergesort
Ordenação estável.
Mergesort é uma aula grátis de C Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.
Ordenação estável
Mergesort é um algoritmo de ordenação por divisão e conquista que divide o vetor ao meio, ordena cada metade e depois as intercala. Ele é O(n log n) em todos os casos e estável.
A etapa de divisão
Divida recursivamente o vetor no ponto médio até que cada parte tenha um elemento. Um único elemento já está ordenado trivialmente, o que constitui o caso base.
A etapa de intercalação
A operação central intercala duas sequências já ordenadas em uma só. Percorra ambas com ponteiros de índice, copiando sempre primeiro o menor elemento da frente.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Por que ele é estável
A intercalação usa a[i] <= a[j]; portanto, quando dois elementos são iguais, ela escolhe primeiro o da sequência da esquerda. Como essa sequência continha os elementos anteriores, a ordem original é preservada.
O controlador recursivo
Mergesort faz chamadas recursivas para cada metade e depois as intercala. Passamos um buffer auxiliar compartilhado para evitar alocá-lo a cada chamada.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Uso de memória
Ao contrário do quicksort, o mergesort precisa de memória extra O(n) para o buffer de intercalação. Essa é sua principal desvantagem para vetores muito grandes quando há pouca memória disponível.
O(n log n) garantido
A recursão sempre divide o vetor ao meio, produzindo log n níveis, e cada nível intercala n elementos. Portanto, o mergesort é O(n log n) nos casos melhor, médio e pior, ao contrário do quicksort.
Contando os níveis de intercalação
O número de níveis de recursão é ceil(log2 n). Vamos calculá-lo para vários tamanhos.
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}Mergesort de baixo para cima
Uma variante iterativa intercala sequências de tamanho 1, depois 2, depois 4, dobrando o tamanho a cada passagem. Ela elimina completamente a recursão e é adequada para listas encadeadas.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Quando escolher o mergesort
Prefira o mergesort quando precisar de:
- O(n log n) garantido, sem casos ruins
- Estabilidade
- Ordenar listas encadeadas (sem necessidade de acesso aleatório)
- Ordenação externa de dados grandes demais para a RAM
Mergesort versus quicksort
O quicksort geralmente é mais rápido na prática e ordena no próprio vetor, mas é instável e pode ter um caso pior desfavorável. O mergesort é estável e tem limite garantido, mas usa memória extra. Escolha com base nas suas restrições.
Verificação rápida
Teste sua compreensão do mergesort.
Recapitulação
Você aprendeu o mergesort.
- Dividir ao meio, ordenar cada parte e depois intercalar
- A intercalação mantém a prioridade da esquerda para chaves iguais, garantindo estabilidade
- O(n log n) garantido em todos os casos
- Custa O(n) de memória extra; é excelente para listas encadeadas e ordenação externa
Aprenda C com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 39
- Aulas
- 144
Perguntas Frequentes
A aula “Mergesort” é grátis?
Sim — o texto completo de “Mergesort” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.
O que vou aprender em “Mergesort”?
Ordenação estável. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar C Academy?
Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Mergesort”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de C Academy?
Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.