Merge sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 1:
{{S|informatica}}
Il '''merge sort''' è un [[algoritmo]] [[algoritmo di ordinamento|di ordinamento]] molto intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.
L'idea alla base del merge sort è il procedimento [[Divide et impera (informatica)|Divide et Impera]], che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.
==Fase 1: Impera==
Supponendo di avere due sequenze già ordinate. Per unirle, l'algoritmo mergesort estrae ripetutamente il minimo delle due sequenze in ingresso e lo pone in una sequenza in uscita.
Il merge sort opera quindi dividendo l'insieme da ordinare in due metà e procedendo all'ordinamento delle medesime ricorsivamente. Quando si sono divise tutte le metà si procede alla loro fusione (merge appunto) costruendo un insieme ordinato.
| |||