Merge Sort in Python

Mon 25 April 2022

Merge Sort

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.

Algoritmo

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.

Merging e splitting

L'algoritmo esegue logicamente questi tre passaggi:

  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

Implementazione (in Python)

L'implementazione in Python dell'algoritmo Merge Sort è la seguente:

def merge_sort(elements):
    if len(elements) > 1:
        # fase 1: splitting
        mid = len(elements) // 2
        left = elements[:mid]
        right = elements[mid:]
        merge_sort(left)
        merge_sort(right)

        # fase 2: merging
        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

    return elements

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.

Prestazioni

L'algoritmo Merge Sort ha una complessità O(n log n) nel suo caso medio e peggiore.

Se andiamo a vedere come si comporta l'algoritmo notiamo che:

  • ogni chiamata alla funzione merge_sort ha complessità O(n)
  • ogni funzione merge_sort richiama se stessa due volte con un numero di elementi di input dimezzati

Conclusioni

L'articolo mostra l'algoritmo di ordinamento Merge Sort che rappresenta un miglioramento rispetto agli algoritmi Bubble Sort ed Insertion Sort.

L'algoritmo rappresenta una soluzione di ordinamento anche per elenchi di dimensioni elevate data la sua complessità O(n log n) nel caso peggiore.

L'implementazione dell'algoritmo è leggermente più complessa rispetto ad altri algoritmi di ordinamento.

Ulteriori algoritmi di ordinamento