Ordinamento a fusione

8.1 Definizione dell'ordinamento a fusione

L'ordinamento a fusione (Merge Sort) è un algoritmo di ordinamento efficiente, stabile e comparativo che utilizza l'approccio "dividi et impera" per ordinare gli elementi. L'algoritmo divide l'array in due metà, ordina ricorsivamente ogni metà, e poi unisce le metà ordinate in un unico array ordinato.

Principio di funzionamento:

Divisione:

• Dividi l'array originale a metà per ottenere due sottoarray.
• Ripeti il processo per ogni sottoarray fino a quando ogni sottoarray non diventa un array di un solo elemento (o vuoto).

Fusione:

• Unisci due sottoarray adiacenti in un unico array ordinato.
• Ripeti il processo di fusione finché non ottieni un unico array ordinato.

Complessità temporale e spaziale dell'ordinamento a fusione

Complessità temporale:

• Nel caso peggiore: O(n log n)
• Nel caso medio: O(n log n)
• Nel caso migliore: O(n log n)

Complessità spaziale:

O(n) — memoria aggiuntiva necessaria per memorizzare i sottoarray temporanei.

8.2 Metodo di fusione discendente

La sequenza originale è ricorsivamente divisa a metà finché non otteniamo sottosequenze di un elemento. Dalle sottosequenze ottenute si formano delle coppie ordinate con il metodo di fusione, poi quartetti ordinati, e così via.

Consideriamo la sequenza:

Dividiamo la sequenza in 2 metà (ricorsivamente, fino a ottenere coppie).

Ogni sottosequenza viene ordinata con il metodo di fusione e otteniamo la sequenza finale.

8.3 Implementazione dell'algoritmo di ordinamento a fusione

Ed è qui che torna utile la ricorsione! È un algoritmo molto buono e veloce rispetto ai precedenti. Divide l'array a metà, ordina entrambe le parti separatamente, e poi unisce rapidamente le parti ordinate.

L'implementazione appare circa così:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Troviamo il centro dell'array
        left_half = arr[:mid]  # Dividiamo l'array in due sottoarray
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Ordiniamo ricorsivamente la parte sinistra
        merge_sort(right_half)  # Ordiniamo ricorsivamente la parte destra
        
        i = j = k = 0
        
        # Fusione delle parti ordinate
        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
        
        # Controllo degli elementi rimanenti
        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

# Esempio di utilizzo:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Array ordinato:", sorted_arr)
# Output: Array ordinato: [3, 9, 10, 27, 38, 43, 82]

Punto chiave all'inizio:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 # Troviamo il centro dell'array
        left_half = arr[:mid] # Dividiamo l'array in due sottoarray right_half = arr[mid:]
        
        merge_sort(left_half)  # Ordiniamo ricorsivamente la parte sinistra
        merge_sort(right_half)  # Ordiniamo ricorsivamente la parte destra

Ecco cosa succede qui:

1. Troviamo il centro dell'array
2. Dividiamo l'array in 2 parti
3. Ordiniamo ciascuna parte separatamente

Questo approccio accelera notevolmente l'algoritmo.