Motivazione

Merge Sort suddivide il problema in sottoproblemi più piccoli, risolve ciascuno di essi e combina i risultati. Questo passaggio di combinazione, che consiste nel fondere due liste già ordinate, è il cuore dell’algoritmo.

Perché imparare Merge Sort?

• Veloce e prevedibile: ha una complessità temporale O(n log n) nel caso migliore, medio e peggiore.
• Stabile: gli elementi uguali mantengono il loro ordine relativo originale.
• Ottimo per grandi quantità di dati: funziona bene quando i dati non entrano in memoria (ordinamento esterno) e con le liste concatenate.
• Dividi e conquista: insegna uno schema usato in molti algoritmi avanzati.