Ordenamiento por fusión

8.1 Definición del ordenamiento por fusión

El ordenamiento por fusión (Merge Sort) es un algoritmo de ordenamiento eficiente, estable y basado en comparaciones, que utiliza el enfoque "divide y vencerás" para ordenar elementos. El algoritmo divide el arreglo en dos mitades, ordena recursivamente cada mitad y luego fusiona las mitades ordenadas en un solo arreglo ordenado.

Principio de funcionamiento:

División:

• Divide el arreglo original por la mitad para obtener dos subarreglos.
• Repite el proceso para cada subarreglo hasta que cada subarreglo sea un arreglo de un solo elemento (o vacío).

Fusión:

• Fusiona dos subarreglos contiguos en un solo arreglo ordenado.
• Repite el proceso de fusión hasta obtener un solo arreglo ordenado.

Complejidad temporal y espacial del ordenamiento por fusión

Complejidad temporal:

• En el peor caso: O(n log n)
• En el caso promedio: O(n log n)
• En el mejor caso: O(n log n)

Complejidad espacial:

O(n) — memoria adicional necesaria para almacenar subarreglos temporales.

8.2 Método de fusión descendente

La secuencia original se divide recursivamente en mitades hasta obtener subsecuencias de 1 elemento. Con las subsecuencias obtenidas, formamos pares ordenados mediante el método de fusión, luego cuartetos ordenados y así sucesivamente.

Consideremos la secuencia:

Dividimos la secuencia en 2 mitades (recursivamente, hasta obtener pares).

Cada subsecuencia la ordenamos mediante el método de fusión y obtenemos la secuencia completa y ordenada.

8.3 Implementación del algoritmo de ordenamiento por fusión

¡Aquí es donde entra en juego la recursividad! Es un algoritmo muy bueno y rápido comparado con los anteriores. Divide el arreglo a la mitad, ordena ambas partes por separado y luego fusiona rápidamente las partes ya ordenadas.

Su implementación se ve más o menos así:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Encontramos el medio del arreglo
        left_half = arr[:mid]  # Dividimos el arreglo en dos subarreglos
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Recursivamente ordenamos la mitad izquierda
        merge_sort(right_half)  # Recursivamente ordenamos la mitad derecha
        
        i = j = k = 0
        
        # Fusión de las mitades ordenadas
        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
        
        # Comprobación de elementos restantes
        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
    return arr

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

Punto clave al principio:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 # Encontramos el medio del arreglo
        left_half = arr[:mid] # Dividimos el arreglo en dos subarreglos right_half = arr[mid:]
        
        merge_sort(left_half)  # Recursivamente ordenamos la mitad izquierda
        merge_sort(right_half)  # Recursivamente ordenamos la mitad derecha

Esto es lo que está ocurriendo aquí:

1. Encontramos el medio del arreglo
2. Dividimos el arreglo en 2 partes
3. Ordenamos cada parte por separado

Este enfoque acelera mucho el algoritmo.