Algoritmi Python

L'ordinamento per fusione (merge sort) in Python

In questa lezione implementerai il merge sort con la strategia divide et impera usando una funzione ricorsiva.

  • Intermedio
  • 3 min di lettura
  • 1 esempio eseguibile

Introduzione

Il problema

Gli ordinamenti semplici rallentano molto quando le liste crescono: raddoppiare i dati quadruplica il lavoro. Il merge sort divide il problema in problemi più piccoli facili da risolvere, e fa crescere il lavoro solo un po' più in fretta dei dati.

Immaginalo così

Il merge sort è come ordinare con degli amici una grande pila di compiti d'esame. Dividi la pila a metà, dai via ogni metà, e loro dividono di nuovo la loro, finché ognuno ha un solo foglio. Poi le coppie di persone uniscono le loro pile ordinate prendendo sempre il foglio in cima più piccolo, finché resta una sola pila ordinata.

Dall'ordinare i compiti al codice
if len(values) <= 1:📄 Un foglio solo è già ordinato
merge_sort(values[:middle])✂️ Dividi la pila e ordina ogni metà
left[left_index] <= right[right_index]🤝 Unisci: prendi il foglio in cima più piccolo
result + left[left_index:] + right[right_index:]📚 Aggiungi ciò che resta dell'altra pila
Dividi fino ai singoli elementi, poi riunisci le pile ordinate.
In una frase

Il merge sort divide una lista a metà, ordina ogni metà in modo ricorsivo e unisce le due metà ordinate, in tempo O(n log n).

Punti chiave

  1. if len(values) <= 1: return values è il caso base che ferma la ricorsione.
  2. merge_sort(values[:middle]) e merge_sort(values[middle:]) ordinano le due metà.
  3. Il ciclo while prende il valore in testa più piccolo da left o da right finché una lista non finisce.
  4. left[left_index:] e right[right_index:] aggiungono i valori rimasti, che sono già ordinati.
  5. <= prende prima da sinistra in caso di parità, il che tiene i valori uguali nel loro ordine originale.

Quando si usa?

  • Ordinare grandi dati in modo prevedibilmente veloce, senza un caso peggiore cattivo.
  • Ordinare liste collegate o dati troppo grandi per la memoria (ordinamento esterno).
  • Imparare il divide et impera, uno schema usato in molti algoritmi.

Quando non serve

  • Codice Python normale: sorted() usa già Timsort, un mix ottimizzato di merge sort e insertion sort.
  • Memoria molto scarsa: il merge sort ha bisogno di spazio extra per le liste unite.

Visualizzatore di L'ordinamento per fusione (merge sort) in Python

O(n log n)

Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.

Codice di esempio

Esegui codice →
main.py
def merge_sort(values):
    if len(values) <= 1:
        return values
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    result = []
    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    return result + left[left_index:] + right[right_index:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Crea un pulsante Run per questo esempio

Risultato dell'esecuzione

[3, 9, 10, 27, 38, 43, 82]

Spiegazione del codice

La funzione ricorsiva divide la lista finché ogni parte ha un solo elemento, perché una lista di un elemento è sempre ordinata. Poi il ciclo while fonde le due sottoliste prendendo sempre l'elemento più piccolo all'inizio di ciascuna. L'algoritmo richiede sempre tempo O(n log n) e O(n) di memoria aggiuntiva.

Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.

Esercizi di approfondimento

Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Dimenticare gli avanzi

Quando una metà finisce, il resto dell'altra metà va perso.

Problema
return result
Correzione
return result + left[left_index:] + right[right_index:]

Hai finito questa lezione?

Segnala come imparata per tenere traccia dei tuoi progressi.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide