Merge sort en C: ejercicio resuelto con divide y vencerás

2026-02-26 4 minutos

Método de ordenamiento merge sort en C

Si buscas merge sort en C ejercicio resuelto, este ejemplo te sirve para entender la idea completa y no solo copiar el código.

Merge sort es un algoritmo recursivo basado en divide y vencerás. Divide el problema en mitades, ordena cada mitad y luego las mezcla. Su rendimiento temporal es O(n log n) en mejor, medio y peor caso. Se atribuye a John von Neumann (1945) y sigue siendo una referencia para entender algoritmos eficientes de ordenación.

Estrategia de merge sort

La estrategia es esta:

Si el array tiene 0 o 1 elemento, ya está ordenado.
Si tiene 2 o más, se divide en dos mitades.
Se ordena cada mitad con el mismo procedimiento.
Se mezclan las dos mitades ordenadas en un solo array final.

Esta forma de trabajar evita comparaciones innecesarias y mantiene un coste estable incluso cuando la entrada ya viene casi ordenada.

Pseudocódigo de merge sort

function merge_sort(A, l, r, aux):
    if l >= r:
        return

    m = l + (r - l) / 2
    merge_sort(A, l, m, aux)
    merge_sort(A, m + 1, r, aux)
    merge(A, l, m, r, aux)

function merge(A, l, m, r, aux):
    i = l
    j = m + 1
    k = l

    while i <= m and j <= r:
        if A[i] <= A[j]:
            aux[k] = A[i]
            i = i + 1
        else:
            aux[k] = A[j]
            j = j + 1
        k = k + 1

    copiar restantes de izquierda
    copiar restantes de derecha
    copiar aux[l..r] en A[l..r]

Enunciado

Implementa merge sort para ordenar un array de enteros en orden ascendente.

Solución en C

#include <stdio.h>
#include <stdlib.h>

static void merge(int a[], int aux[], int l, int m, int r) {
    int i = l;
    int j = m + 1;
    int k = l;

    while (i <= m && j <= r) {
        if (a[i] <= a[j]) {
            aux[k++] = a[i++];
        } else {
            aux[k++] = a[j++];
        }
    }

    while (i <= m) {
        aux[k++] = a[i++];
    }

    while (j <= r) {
        aux[k++] = a[j++];
    }

    for (i = l; i <= r; i++) {
        a[i] = aux[i];
    }
}

static void merge_sort_rec(int a[], int aux[], int l, int r) {
    if (l >= r) {
        return;
    }

    int m = l + (r - l) / 2;
    merge_sort_rec(a, aux, l, m);
    merge_sort_rec(a, aux, m + 1, r);
    merge(a, aux, l, m, r);
}

void merge_sort(int a[], int n) {
    if (n <= 1) {
        return;
    }

    int *aux = malloc((size_t)n * sizeof(int));
    if (!aux) {
        fprintf(stderr, "Error: no se pudo reservar memoria auxiliar\n");
        exit(EXIT_FAILURE);
    }

    merge_sort_rec(a, aux, 0, n - 1);
    free(aux);
}

int main(void) {
    int a[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(a) / sizeof(a[0]);

    merge_sort(a, n);

    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Salida esperada

3 9 10 27 38 43 82

Desglose rápido del código

merge_sort reserva un array auxiliar una sola vez.
merge_sort_rec divide el problema en mitades hasta llegar a subarrays de tamaño 1.
merge une dos mitades ya ordenadas comparando elementos en tiempo lineal.

Complejidad de merge sort en C

Tiempo (mejor, medio y peor caso): O(n log n)
Memoria extra: O(n)

Por eso merge sort se usa cuando quieres rendimiento predecible y estabilidad en la ordenación.

Errores frecuentes

Usar mal los límites de cada mitad (l, m, r).
Olvidar copiar de aux a a al final del merge.
Escribir m = (l + r) / 2 sin pensar en overflow en índices grandes.
No contemplar el caso base y entrar en recursividad infinita.

Aplicación práctica

Merge sort te conviene cuando:

necesitas una ordenación estable,
quieres comportamiento temporal consistente,
trabajas con datos grandes y no te importa usar memoria auxiliar.

Si priorizas memoria y promedio rápido, quicksort puede ser mejor según el caso.

Siguiente ejercicio recomendado

Práctica guiada y siguiente paso

Si quieres una ruta completa con progresión real de dificultad:

FAQ

¿Merge sort en C sirve para entrevistas técnicas?

Sí. Es muy común en entrevistas y pruebas porque combina recursividad, índices y análisis de complejidad.

¿Merge sort siempre tarda O(n log n)?

Sí, en tiempo asintótico. Esa es una de sus ventajas frente a otros algoritmos de ordenación.

¿Cómo practicar merge sort para dominarlo de verdad?

Empieza con arrays pequeños, traza cada merge a mano, y luego prueba repetidos, negativos y arrays inversos.