Algoritmo di ordinamento Merge sort in Python

Il Merge Sort è uno degli algoritmi di ordinamento più efficienti e stabili, utilizzato ampiamente in contesti sia accademici che pratici. Sviluppato da John von Neumann nel 1945, è un esempio classico di algoritmo divide et impera.

Questa guida esplorerà in dettaglio il funzionamento del Merge Sort, come implementarlo in Python, e i suoi vantaggi e svantaggi.

Il merge sort è un algoritmo di ordinamento che segue il paradigma divide et impera. Divide la lista in sotto-liste più piccole, le ordina ricorsivamente, e poi le combina (merge) per ottenere una lista ordinata. La sua complessità temporale è O(n log n) sia nel caso peggiore che nel caso medio, rendendolo molto efficiente.

Funzionamento del Merge sort

• Divisione: Dividi la lista a metà fino ad ottenere sotto-liste di un solo elemento.

• Conquista: Ordina le sotto-liste ricorsivamente.

• Combina: Combina le sotto-liste ordinate in una lista ordinata unica.

Consideriamo una lista [5, 3, 8, 4, 2, 7, 1, 6].

• Passo 1: Dividi la lista in due metà [5, 3, 8, 4] e [2, 7, 1, 6].

• Passo 2: Dividi ulteriormente queste metà fino ad ottenere liste singole: [5], [3], [8], [4], [2], [7], [1], [6].

• Passo 3: combina:

  • Combina [5] e [3] per ottenere [3, 5].

  • Combina [8] e [4] per ottenere [4, 8].

  • Combina [2] e [7] per ottenere [2, 7].

  • Combina [1] e [6] per ottenere [1, 6].

  • Continua a combinare fino ad ottenere la lista ordinata finale [1, 2, 3, 4, 5, 6, 7, 8].

Implementazione del Merge sort in Python

Implementare il Merge Sort in Python implica la definizione di una funzione ricorsiva che divida la lista e una funzione che combini le sotto-liste ordinate. Ecco un esempio di codice:

def merge_sort(lista):
    if len(lista) <= 1:
        return lista

    mid = len(lista) // 2
    left_half = merge_sort(lista[:mid])
    right_half = merge_sort(lista[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_list = []
    left_index = right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            sorted_list.append(left[left_index])
            left_index += 1
        else:
            sorted_list.append(right[right_index])
            right_index += 1

    sorted_list.extend(left[left_index:])
    sorted_list.extend(right[right_index:])
    return sorted_list

# Esempio di utilizzo
lista = [5, 3, 8, 4, 2, 7, 1, 6]
ordinata = merge_sort(lista)
print("Lista ordinata:", ordinata)

Spiegazione del codice:

• Base Case: if len(lista) <= 1: Se la lista ha un solo elemento o è vuota, è già ordinata.

• Divisione: mid = len(lista) // 2: Calcola il punto medio per dividere la lista.

• Ricorsione: left_half = merge_sort(lista[:mid]) e right_half = merge_sort(lista[mid:]): Ordina ricorsivamente le due metà.

• Combina: return merge(left_half, right_half): Combina le due metà ordinate in una lista ordinata unica.

La funzione merge combina due liste ordinate in una sola lista ordinata.

Vantaggi e svantaggi del Merge sort

Vantaggi:

• Ha una complessità temporale di O(n log n) per tutti i casi, rendendolo molto efficiente.

• È un algoritmo di ordinamento stabile, il che significa che preserva l'ordine relativo degli elementi uguali.

• È facilmente parallelizzabile, poiché ogni sotto-lista può essere ordinata indipendentemente.

Svantaggi:

• Richiede spazio aggiuntivo O(n) per memorizzare le sotto-liste durante il processo di combinazione, rendendolo meno efficiente in termini di memoria rispetto ad algoritmi in-place come il Quick Sort.

• Potrebbe essere meno efficiente per piccoli dataset rispetto ad algoritmi come l'Insertion Sort.

Ottimizzazioni del Merge sort

Esistono diverse tecniche per ottimizzare il Merge Sort:

• Merge sort in-place: Ridurre l'uso di memoria combinando le sotto-liste direttamente nella lista originale.

• Utilizzare l'Insertion sort per ordinare sotto-liste molto piccole, migliorando le prestazioni complessive.

• Implementare il merge sort in parallelo per sfruttare la potenza dei processori multi-core.

Conclusione

Il Merge Sort è un algoritmo di ordinamento potente e versatile, particolarmente efficace per ordinare grandi dataset grazie alla sua complessità temporale di O(n log n). La sua stabilità e facilità di parallelizzazione lo rendono una scelta eccellente in molti contesti pratici. Tuttavia, il suo uso di memoria aggiuntiva può essere un problema in ambienti con risorse limitate.