Tutorial su Merge Sort in Python

Ordinare i dati è una delle operazioni più comuni nel lavoro quotidiano di chi si occupa di dati. Spesso dobbiamo mostrare i dati in un certo ordine per ricavare informazioni significative. Per fortuna, oggi non dobbiamo svolgere questo compito manualmente. I computer possono fare la magia per noi con prestazioni imbattibili.

Esistono diverse strategie per ordinare i dati. In questo tutorial analizzeremo una delle tecniche di ordinamento più efficaci. L’algoritmo di “merge sort” utilizza una strategia divide et impera per ordinare un array non ordinato, suddividendolo prima in array più piccoli, che poi vengono uniti nell’ordine corretto. 

Nelle prossime sezioni parleremo di tutti i dettagli dell’algoritmo merge sort, di come appare in Python e di alcuni consigli pratici per un’implementazione senza intoppi.

Che cos’è il Merge Sort?

Esistono molti algoritmi di ordinamento, ma è difficile trovarne uno che si comporti meglio del merge sort. Non sorprende che questo algoritmo sia usato in ogni tipo di applicazione reale, come l’ordinamento di grandi database o l’organizzazione dei file su un normale computer.

L’algoritmo si basa sul paradigma divide et impera, che si può suddividere in tre parti:

• Divide: questo processo divide il problema in sotto-problemi più piccoli. 
• Conquer: i sotto-problemi vengono risolti ricorsivamente. 
• Combine: le soluzioni dei sotto-problemi vengono combinate per ottenere la soluzione finale.

Strategia divide et impera

Vediamo come funziona il merge sort. Supponiamo di voler ordinare i seguenti numeri applicando l’algoritmo merge sort. L’algoritmo divide ricorsivamente i dati in due parti e continua a dividere finché ogni lista non ha un solo elemento. Poi li combiniamo ordinandoli in un’altra lista.

Problema di Merge Sort. Fonte: DataCamp

Complessità temporale e spaziale del Merge Sort

È impossibile sapere in anticipo qual è l’algoritmo di ordinamento che funziona meglio per un determinato problema. Oltre all’algoritmo stesso, vanno considerate diverse variabili, tra cui il linguaggio di programmazione usato per scrivere il codice, l’hardware su cui viene eseguito e le particolarità dei dati da ordinare. 

Anche se non possiamo prevedere il tempo di esecuzione esatto di un algoritmo di ordinamento, possiamo comunque confrontare le prestazioni di vari algoritmi analizzando la complessità temporale e spaziale.

Complessità temporale del merge sort

Come spiegato in una guida a parte su Big O e complessità temporale, l’obiettivo dell’analisi della complessità temporale non è prevedere il tempo di esecuzione esatto di un algoritmo, ma valutare quanto è efficiente analizzando come cambia il suo tempo di esecuzione all’aumentare della quantità di dati in input.

L’analisi della complessità temporale si esprime con la notazione Big O, una notazione matematica che descrive la velocità con cui una funzione cresce o decresce. Il merge sort ha complessità temporale log-lineare o linearitmica, indicata come O(N log(N)), dove N è il numero di elementi nella lista. La lettera “O” sta per “ordine” di crescita. 

Nell’analisi della complessità temporale, la complessità linearitmica si comporta all’incirca in modo simile a quella lineare, il che significa che l’esecuzione sarà direttamente proporzionale alla quantità di dati. Dunque, se la quantità di dati raddoppia, anche il tempo necessario all’algoritmo per elaborare i dati dovrebbe raddoppiare, cioè il numero di divisioni e unioni raddoppierà.

Poiché la complessità temporale del merge sort si comporta linearmente, la sua complessità rimane la stessa nei casi migliore, medio e peggiore. Ciò significa che, indipendentemente dall’ordine dell’input, l’algoritmo impiegherà sempre lo stesso numero di passaggi per completare.

Complessità spaziale del merge sort

Infine, oltre al tempo necessario per completare il compito, un altro aspetto importante quando si analizza la complessità di un algoritmo è stimare quanta memoria richiederà man mano che il problema cresce. 

Questo è coperto dai concetti di complessità spaziale e spazio ausiliario. Il secondo si riferisce allo spazio extra o temporaneo utilizzato da un algoritmo, mentre il primo si riferisce allo spazio totale occupato dall’algoritmo rispetto alla dimensione dell’input. In altre parole, la complessità spaziale include sia lo spazio ausiliario sia lo spazio usato dall’input.

Il merge sort ha una complessità spaziale di O(N). Questo perché utilizza un array ausiliario di dimensione N per unire le metà ordinate dell’array di input. L’array ausiliario viene usato per memorizzare il risultato unito e l’array di input viene sovrascritto con il risultato ordinato.

Implementazione di Merge Sort in Python

Implementiamo l’algoritmo merge sort in Python. Ci sono diversi modi per codificare l’algoritmo; tuttavia, ci atterremo a quello basato sulla ricorsione, che è probabilmente il più facile da capire e richiede meno righe di codice rispetto ad altre alternative basate sull’iterazione.

Capire la ricorsione nel merge sort

Se sei alle prime armi, in programmazione la ricorsione avviene quando una funzione chiama se stessa. Puoi consultare il nostro tutorial sulla comprensione delle funzioni ricorsive in Python per scoprire tutto su queste potenti funzioni.

Per implementare il merge sort, definiamo prima il caso base: se la lista ha un solo elemento, è già ordinata, quindi ritorniamo immediatamente. Altrimenti, dividiamo la lista in due metà, left_half e right_half, e chiamiamo merge_sort() ricorsivamente su ciascuna. Questo processo continua finché tutte le sottoliste contengono un solo elemento.

Una volta ottenute queste sottoliste ordinate, iniziamo il processo di fusione. Per farlo, inizializziamo tre variabili indice: i per tracciare la posizione in left_half, j per right_half e k per la lista finale unita. Quindi confrontiamo gli elementi di entrambe le metà. Se l’elemento corrente in left_half è più piccolo, lo inseriamo in my_list[k] e avanziamo i. Altrimenti, prendiamo l’elemento da right_half, lo mettiamo in my_list[k] e incrementiamo j. Dopo ogni confronto, spostiamo k avanti alla posizione successiva nella lista finale.

Questo processo continua finché non abbiamo confrontato tutti gli elementi di una delle due metà. Se rimangono elementi in left_half o in right_half, li aggiungiamo direttamente alla lista finale, assicurandoci di non lasciare indietro alcun dato. Poiché il merge sort opera in modo ricorsivo, questo processo di unione viene eseguito a ogni livello di ricorsione fino a quando l’intera lista non è ordinata.

Implementazione in Python

Di seguito trovi il codice che usa come esempio la lista non ordinata del diagramma precedente:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]Offerto da

Merge Sort vs altri algoritmi di ordinamento

Il merge sort è un algoritmo di ordinamento piuttosto veloce, particolarmente adatto a grandi database, ed è spesso usato come benchmark per altri algoritmi. Tuttavia, quando si tratta di liste più corte, le sue prestazioni tendono a essere inferiori rispetto ad altri algoritmi di ordinamento.

Nella tabella seguente trovi un confronto tra il merge sort e altri popolari algoritmi di ordinamento.

Applicazioni pratiche del Merge Sort

Il merge sort ha prestazioni elevate nell’ordinare liste grandi, ma la sua efficienza diminuisce quando si lavora con liste più piccole. Allo stesso modo, tende a essere meno efficiente in scenari in cui nelle liste di input c’è già un certo grado di ordine, poiché il merge sort eseguirà gli stessi passaggi a prescindere dall’ordine della lista.

Un ottimo caso d’uso in cui il merge sort è particolarmente utile sono le liste collegate (linked list). Una linked list è una struttura dati che comprende una connessione di nodi collegati linearmente tra loro. Ogni nodo contiene i dati e il collegamento per connetterlo al nodo successivo.

Il merge sort è preferito per le linked list perché richiede solo accesso sequenziale ai dati, in linea con la natura delle linked list. Inoltre, il merge sort è un algoritmo di ordinamento stabile (cioè preserva l’ordine relativo degli elementi uguali nell’output ordinato), un aspetto molto importante per mantenere l’ordine delle linked list.

Errori comuni e troubleshooting

L’algoritmo merge sort è piuttosto lineare e i margini di miglioramento del codice sono limitati. Tuttavia, puoi aumentare la sofisticazione della tua strategia di ordinamento tenendo conto della dimensione dei dati in input. 

Abbiamo già stabilito che il merge sort funziona meglio con dataset più grandi. Per dataset piccoli, altri algoritmi di ordinamento con complessità O(N^2), come l’insertion sort, possono funzionare meglio. In questo caso, ti basterebbe creare una soglia di dimensione al di sotto della quale sceglieresti l’algoritmo di insertion sort invece di merge sort.

A parte questo, una buona idea da esplorare è la parallelizzazione. I passaggi del merge sort possono essere facilmente parallelizzati con la giusta potenza di calcolo, riducendo così il tempo di completamento. Leggi la nostra guida CPU vs GPU per saperne di più sull’elaborazione parallela. 

Conclusione

Il merge sort è uno degli algoritmi di ordinamento più efficaci e popolari, ma c’è molto altro da imparare nel meraviglioso e in continua espansione universo degli algoritmi. Se ti interessano gli aspetti tecnici degli algoritmi, come funzionano e la loro complessità, virtù e limiti, queste risorse di DataCamp possono aiutarti a proseguire l’apprendimento:

• Corso introduttivo su strutture dati e algoritmi 
• Skill Track Programmazione Python
• Skill Track Fondamenti di dati in Python
• Corso Python intermedio
• Career Track Data Analyst in Python 
• Big O e complessità temporale