Edición didáctica en español. El código y sus salidas conservan el original.

Merge sort en C

Divide, ordena y combina arrays con un tiempo de O(N log N).

Merge sort divide el intervalo por la mitad hasta obtener partes de un elemento. Al regresar de la recursión, combina dos partes ordenadas eligiendo repetidamente el menor de sus primeros elementos pendientes.

La combinación debe copiar también los elementos que sobren en cualquiera de las mitades. Si eliges primero el elemento de la mitad izquierda cuando hay empate, puedes conservar la estabilidad del ordenamiento. El método habitual requiere O(N) de espacio auxiliar, además de la pila de recursión.

Comprueba tamaños impares, valores repetidos y límites del buffer temporal. El tiempo es O(N log N) incluso cuando la entrada ya está ordenada, salvo optimizaciones adicionales.

Código C

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

int merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    if (L == NULL || R == NULL) {
        free(L);
        free(R);
        return 0;
    }

    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
    return 1;
}

int mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        if (!mergeSort(arr, l, m) || !mergeSort(arr, m + 1, r)) return 0;
        return merge(arr, l, m, r);
    }
    return 1;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    if (!mergeSort(arr, 0, n - 1)) {
        fputs("Memory allocation failed.\n", stderr);
        return EXIT_FAILURE;
    }
    printf("MergeSorted Array:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Abrir en el compilador

Salida esperada

MergeSorted Array:
3 9 10 27 38 43 82

Preguntas frecuentes

¿Por qué el código y la salida siguen en inglés?

Las palabras clave, los identificadores y los textos que verifican las pruebas se conservan para no cambiar el programa. Las explicaciones y los controles están traducidos.