Ordinamento per fusione
Divide la lista a metà, ordina ogni metà, poi fonde le due metà ordinate in un'unica lista ordinata.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- sì
- no
Caso migliore: come cresce il tempo con la dimensione n della lista quando l'input è il più facile per questo algoritmo.
Caso medio: crescita tipica del tempo con n. Con n², raddoppiare il numero di valori quadruplica circa il tempo; n log n cresce molto meno.
Caso peggiore: la crescita sull'input più difficile. Utile quando la velocità non deve mai calare.
Spazio: quanta memoria extra serve oltre alla lista. 1 vuol dire poche variabili, n una copia della lista.
Stabile: due valori uguali mantengono il loro ordine originale. Conta quando si ordinano record in base a un solo campo.
Sul posto: ordina dentro la lista stessa, senza una seconda lista.
- confronto
- spostamento
- al suo posto finale
↓ dividi ↓ fondi Fusioni fatte: 0 su 23
Premi Riproduci: le linee mostrano come cresce il costo
Premi Riproduci o avanza passo passo.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
Prova così: Scegli pochi valori unici. Tra due valori uguali si prende prima quello della metà sinistra, quindi i valori uguali mantengono l'ordine.
Come funziona
Continua a dividere la lista finché ogni pezzo ha un solo valore, che è già ordinato. Poi fonde i pezzi a due a due: confronta i primi valori dei due pezzi e prende il più piccolo, ancora e ancora. La riga sollevata nell'animazione è lo spazio extra usato durante la fusione.
Quando conviene usarlo
Quando serve una velocità che resti buona anche nel caso peggiore e i valori uguali devono mantenere il loro ordine. Python e Java usano entrambi una versione dell'ordinamento per fusione. Il suo difetto è la memoria extra che richiede.