Merge Sort in Python

Questo video accompagna la guida Merge Sort in Python e riprende i passaggi principali con una spiegazione più diretta e visuale.

Sintesi del video

Merge Sort è un algoritmo di ordinamento sviluppato da John Von Neumann nel 1940. L’articolo descrive la strategia dell’algoritmo proponendo un’implementazione in Python.

Punti trattati

• Algoritmo
• Implementazione
• Prestazioni

Testo di supporto

L’algoritmo Merge Sort è un algoritmo di ordinamento, sviluppato nel 1940 da John Von Neumann che consente di aggiornare una lista di elementi omogenei ricorrendo alla strategia divide et impera.

Rispetto agli algoritmi Bubble Sort ed Insertion Sort, che hanno prestazioni migliori con liste parzialmente ordinate, le prestazioni dell’algoritmo di Merge Sort non dipendono dal fatto che i dati di input siano ordinati.

L’algoritmo Merge Sort è basato sulla strategia divide et impera; l’algoritmo per ordinare gli elementi lavora su due fasi:

1. splitting: divide ricorsivamente la lista fino a quando la dimensione dei dati risulta inferiore rispetto ad una certa soglia
2. merging: elabora i dati fino a restituire il risultato finale

Se ad esempio volessimo applicare le due fasi alla lista [56, 52, 25, 69, 14, 3], l’elaborazione prevede i seguenti passaggi di ordinamento.

1. Divide la lista di elementi in parti uguali
2. Ricorsivamente divide le liste finchè tutte le sottoliste abbiano lunghezza pari ad 1
3. Unisce le sottoliste ordinate in una lista ordinata e le restituisce

a = b = c = 0 while a < len(left) and b < len(right): if left[a] < right[b]: elements[c] = left[a] a += 1 else: elements[c] = right[b] b += 1 c += 1

while a < len(left): elements[c] = left[a] a += 1 c += 1

while b < len(right): elements[c] = right[b] b += 1 c += 1

L’implementazione prevede delle chiamate ricorsive alla funzione finchè la lunghezza della lista degli elementi non risulta pari ad 1. A quel punto si avvia la fase di merging andando ad ordinare le sottoliste che man mano si vanno a formare.

Approfondimento scritto

Per comandi, esempi e passaggi completi puoi leggere l’articolo collegato: Merge Sort in Python .