Complessità temporale e spaziale

Complessità temporale:

• Caso migliore, medio e peggiore: O(n log n)
  • L'array viene diviso a metà circa log n volte e a ogni livello si eseguono O(n) operazioni per effettuare la fusione. Il tempo di esecuzione non dipende dall'ordine degli elementi in input.

Complessità spaziale:

• O(n)
  • A differenza degli algoritmi di ordinamento in-place, Merge Sort crea nuovi array durante la fusione, quindi richiede memoria aggiuntiva proporzionale alla dimensione dell'input.

Riepilogo:

• Merge Sort è veloce e prevedibile: O(n log n) in ogni caso.
• È stabile, quindi gli elementi uguali mantengono il loro ordine.
• Il compromesso è l'uso di memoria aggiuntiva O(n) per la fusione.