El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

Introducción

El ordenamiento por mezcla, conocido en inglés como Merge Sort, es un algoritmo de ordenamiento basado en la técnica de Divide y Vencerás. Este algoritmo es notable por su eficiencia y estabilidad, y es especialmente útil para ordenar grandes conjuntos de datos.

Objetivos

Comprender el funcionamiento del algoritmo Merge Sort.
Implementar Merge Sort en un lenguaje de programación.
Analizar la complejidad temporal y espacial de Merge Sort.

Conceptos Clave

Divide y Vencerás

El principio de Divide y Vencerás consiste en dividir un problema en subproblemas más pequeños, resolver estos subproblemas de manera recursiva y luego combinar las soluciones para obtener la solución del problema original.

Pasos del Algoritmo Merge Sort

Dividir: Dividir el conjunto de datos en dos mitades.
Vencer: Ordenar cada mitad recursivamente aplicando Merge Sort.
Combinar: Combinar las dos mitades ordenadas para formar un solo conjunto ordenado.

Implementación de Merge Sort

A continuación, se presenta una implementación de Merge Sort en Python:

def merge_sort(arr):
    if len(arr) > 1:
        # Dividir el arreglo en dos mitades
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        # Ordenar cada mitad
        merge_sort(left_half)
        merge_sort(right_half)

        # Combinar las dos mitades ordenadas
        i = j = k = 0

        # Copiar los datos a los arreglos temporales left_half y right_half
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Verificar si quedó algún elemento
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Ejemplo de uso
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Arreglo ordenado:", arr)

Explicación del Código

División del Arreglo: La función merge_sort divide el arreglo en dos mitades hasta que cada subarreglo contiene un solo elemento.
Ordenamiento Recursivo: Cada mitad se ordena recursivamente llamando a merge_sort sobre sí misma.
Combinación: Los elementos de las dos mitades se combinan en un solo arreglo ordenado.

Complejidad del Algoritmo

Complejidad Temporal

Caso Promedio y Peor Caso: O(n log n)
Mejor Caso: O(n log n)

Complejidad Espacial

Espacio Auxiliar: O(n)

Ejercicios Prácticos

Ejercicio 1: Implementación Básica

Implementa el algoritmo Merge Sort en otro lenguaje de programación de tu elección (por ejemplo, Java, C++).

Ejercicio 2: Análisis de Complejidad

Analiza la complejidad temporal y espacial del algoritmo Merge Sort para un conjunto de datos de tamaño n = 1000.

Ejercicio 3: Variaciones del Algoritmo

Investiga y prueba una variación del algoritmo Merge Sort, como el Merge Sort de fondo hacia arriba (Bottom-Up Merge Sort).

Soluciones

Solución al Ejercicio 1

// Implementación en Java
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; ++i)
            leftArray[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            rightArray[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Arreglo ordenado: " + Arrays.toString(arr));
    }
}

Solución al Ejercicio 2

Para un conjunto de datos de tamaño n = 1000, la complejidad temporal de Merge Sort es O(1000 log 1000), lo que resulta en aproximadamente 1000 * 10 = 10000 operaciones. La complejidad espacial sigue siendo O(1000).

Solución al Ejercicio 3

El Bottom-Up Merge Sort es una variación iterativa del Merge Sort que no utiliza recursión. Investiga y prueba esta variación para entender sus ventajas y desventajas.

Conclusión

El algoritmo Merge Sort es una herramienta poderosa para ordenar grandes conjuntos de datos de manera eficiente. Su enfoque de Divide y Vencerás permite una complejidad temporal de O(n log n) en el peor de los casos, lo que lo hace superior a muchos otros algoritmos de ordenamiento en términos de rendimiento. Además, su estabilidad y eficiencia espacial lo convierten en una opción ideal para diversas aplicaciones.

Ordenamiento por Mezcla (Merge Sort)