Merge sort

Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Merge sort
Esempio di merge sort con una lista di numeri casuali. Innanzitutto, si divide l'elenco nell'unità più piccola (1 elemento), quindi si confronta ogni elemento con l'elenco adiacente per ordinare e unire i due elenchi adiacenti. Infine, tutti gli elementi vengono ordinati e uniti.
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	${\displaystyle \Theta (n\log n)}$
Caso ottimo temporalmente	${\displaystyle \Theta (n\log n)}$
Caso medio temporalmente	${\displaystyle \Theta (n\log n)}$
Caso peggiore spazialmente	${\displaystyle \Theta (n)}$
Ottimale	In alcuni casi
Manuale

Il merge sort è un algoritmo di ordinamento basato su confronti che utilizza un processo di risoluzione ricorsivo, sfruttando la tecnica del Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi della stessa natura di dimensione via via più piccola. Fu inventato da John von Neumann nel 1945. Una descrizione dettagliata e un'analisi della versione bottom-up dell'algoritmo apparve in un articolo di Goldstine e Neumann già nel 1948.