• +34 685 967 885
  • +34 695 898 191
  • antgarprats@gmail.com
  • Antonio García Prats

algoritmo merge sort en c

Merge Sort en C

El algoritmo Merge Sort es un algoritmo de ordenamiento eficiente basado en el paradigma «Divide y vencerá». Fue desarrollado por John von Neumann en 1945 y es ampliamente utilizado debido a su complejidad de tiempo O(n log n) en todos los casos (mejor, peor y promedio).

Fundamentos del algoritmo

El algoritmo Merge Sort divide el arreglo en mitades recursivamente hasta que cada subarreglo tiene un solo elemento o está vacío. Luego, fusiona (“merge”) estas mitades ordenadas en una sola estructura ordenada.

Implementación en C

A continuación, presentamos una implementación en C de Merge Sort, explicando paso a paso el código.

#include <stdio.h>

// Función para fusionar dos subarreglos ordenados en un solo arreglo ordenado
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;  // Tamaño del primer subarreglo
    int n2 = right - mid;      // Tamaño del segundo subarreglo

    // Arreglos temporales
    int L[n1], R[n2];

    // Copiar datos a los arreglos temporales
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Fusionar los subarreglos en el arreglo original
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copiar los elementos restantes de L[]
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copiar los elementos restantes de R[]
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Función recursiva para aplicar Merge Sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // Encuentra el punto medio

        // Ordenar la primera y segunda mitad recursivamente
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Fusionar las mitades ordenadas
        merge(arr, left, mid, right);
    }
}

// Función para imprimir un arreglo
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Programa principal para probar Merge Sort
int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Arreglo original: \n");
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    printf("Arreglo ordenado: \n");
    printArray(arr, size);
    return 0;
}

Explicación del código

merge(): Se encarga de combinar dos subarreglos ordenados en un solo arreglo ordenado.

– Se crean arreglos temporales L[] y R[] para almacenar los elementos de las dos mitades.

– Se copian los datos en estos arreglos.

– Se comparan los elementos de L[] y R[] para fusionarlos en orden.

– Se copian los elementos restantes si alguna de las mitades aún tiene datos pendientes.

mergeSort(): Es la función recursiva que divide el arreglo en mitades y las ordena.

– Divide el arreglo en dos partes hasta que cada parte tiene un solo elemento.

– Llama recursivamente a mergeSort para cada mitad.

– Luego, llama a merge() para combinar las mitades ordenadas.

printArray(): Función auxiliar para imprimir el arreglo en consola.

main(): Función principal del programa.

– Define un arreglo de prueba.

– Muestra el arreglo original.

– Llama a mergeSort() para ordenar el arreglo.

– Muestra el arreglo ordenado después del proceso.

    Complejidad del Algoritmo

    El algoritmo Merge Sort tiene una complejidad de O(n log n) en todos los casos:

    División del problema: Cada paso divide el arreglo en dos partes, lo que toma log n pasos.

    Fusión: Cada nivel de la recursión fusiona n elementos en total.

    Complejidad total: O(n log n).


    El algoritmo Merge Sort es ideal para manejar grandes volúmenes de datos debido a su eficiencia garantizada de O(n log n). Su implementación en C sigue el principio de Divide y vencerás, lo que lo hace modular y fácil de entender.

    ¿Te gustaría más ejemplos o una comparación con otros algoritmos de ordenamiento?. ¡Déjame tu comentario!.

    Deja una respuesta

    Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *