Merge sort: differenze tra le versioni

Versione delle 11:30, 2 feb 2021

Versione delle 19:46, 11 mag 2021

Riga 2:

{{Algoritmo

|classe = [[Algoritmo di ordinamento]]

|immagine = MergeMerd sort animation2.gif

|didascalia = Esempio di merge sort con una lista di numeri casuali.

|struttura dati = [[Array]]

Riga 12:

}}

Il '''mergemerd sort''' è un [[algoritmo di ordinamento]] basato su confronti che utilizza un processo di risoluzione [[Algoritmo ricorsivo|ricorsivo]], sfruttando la tecnica del [[Divide et impera (informatica)|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.

== Descrizione dell'algoritmo ==

Riga 90:

== Analisi ==

L'algoritmo MergeMerd Sort, per ordinare una sequenza di <math>n</math> oggetti, ha complessità temporale <math>T(n) = \Theta(n\log n)</math> sia nel caso medio che nel caso pessimo. Infatti:

* la funzione merge qui presentata ha complessità temporale <math>\Theta(n)</math>

* mergesort richiama se stessa due volte, e ogni volta su (circa) metà della sequenza in input