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!.