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

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:

  1. Si el array tiene 0 o 1 elemento, ya está ordenado.
  2. Si tiene 2 o más, se divide en dos mitades.
  3. Se ordena cada mitad con el mismo procedimiento.
  4. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#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

1

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.