Mergesort
Ordenamiento estable
Mergesort es una lección gratuita de C Academy en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.
Ordenación estable
Mergesort es un algoritmo de ordenación basado en divide y vencerás que divide el arreglo por la mitad, ordena cada mitad y después las fusiona. Tiene complejidad O(n log n) en todos los casos y es estable.
El paso de división
Divida recursivamente el arreglo por el punto medio hasta que cada fragmento tenga un elemento. Un solo elemento ya está ordenado de forma trivial, y constituye el caso base.
El paso de fusión
La operación principal fusiona dos secuencias ya ordenadas en una sola. Recorra ambas con punteros de índice y copie siempre primero el elemento inicial más pequeño.
#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 qué es estable
La fusión utiliza a[i] <= a[j], por lo que, cuando dos elementos son iguales, toma primero el de la secuencia izquierda. Como dicha secuencia contenía los elementos anteriores, se conserva el orden original.
El controlador recursivo
Mergesort aplica recursividad a cada mitad y después las fusiona. Se pasa un búfer auxiliar compartido para evitar asignar memoria en cada llamada.
#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 memoria
A diferencia de quicksort, mergesort necesita memoria adicional O(n) para el búfer de fusión. Este es su principal inconveniente para arreglos muy grandes cuando la memoria es limitada.
O(n log n) garantizado
La recursividad siempre divide el arreglo por la mitad, lo que produce log n niveles, y en cada nivel se fusionan n elementos. Por tanto, mergesort es O(n log n) en los casos mejor, promedio y peor, a diferencia de quicksort.
Contar los niveles de fusión
El número de niveles de recursividad es ceil(log2 n). Vamos a calcularlo para varios tamaños.
#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 ascendente
Una variante iterativa fusiona secuencias de tamaño 1, después de tamaño 2 y luego de tamaño 4, duplicando el tamaño en cada pasada. Evita por completo la recursividad y resulta adecuada para listas enlazadas.
#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;
}Cuándo elegir mergesort
Prefiera mergesort cuando necesite:
- O(n log n) garantizado, sin casos desfavorables
- Estabilidad
- Ordenar listas enlazadas (no se necesita acceso aleatorio)
- Ordenación externa de datos demasiado grandes para la RAM
Mergesort frente a quicksort
Quicksort suele ser más rápido en la práctica y ordena en el propio arreglo, pero no es estable y puede tener un caso peor desfavorable. Mergesort es estable y ofrece un límite garantizado, pero utiliza memoria adicional. Elija según sus restricciones.
Comprobación rápida
Compruebe su comprensión de mergesort.
Resumen
Ha aprendido mergesort.
- Dividir por la mitad, ordenar cada parte y después fusionarlas
- La fusión da prioridad a la izquierda cuando las claves son iguales, lo que proporciona estabilidad
- O(n log n) garantizado en todos los casos
- Utiliza memoria adicional O(n); es excelente para listas enlazadas y ordenación externa
Aprende C con un tutor de IA — gratis
Escribe y ejecuta código real en tu navegador, obtén ayuda instantánea de un tutor de IA disponible 24/7 y continúa donde lo dejaste en la web o en la aplicación.
- Cursos
- 39
- Lecciones
- 144
Preguntas frecuentes
¿La lección «Mergesort» es gratis?
Sí — el texto completo de «Mergesort» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Mergesort»?
Ordenamiento estable Practicas C Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar C Academy?
No se requiere experiencia previa. C Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Mergesort»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de C Academy?
Sí. Cada lección de C Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.