L'ordinamento di unione è un algoritmo di ordinamento efficiente, generico e basato sul confronto. Si tratta di un paradigma algoritmico "divide et impera" sviluppato da John von Neumann nel 1945. Il merge sort funziona suddividendo ricorsivamente un elenco in più sottoelenchi fino a quando ciascun sottoelenco è costituito da un solo elemento e unendo tali sottoelenchi in un ordine naturale per produrre l'elenco ordinato.
La complessità del tempo di esecuzione dell'ordinamento di unione è considerata ottimale, il che significa che non può essere eseguita più velocemente della complessità del tempo O(n log n). Ciò lo rende una scelta popolare per l'ordinamento di set di dati di grandi dimensioni. L'ordinamento di unione è un algoritmo di ordinamento stabile, il che significa che preserva l'ordinamento degli elementi duplicati nell'elenco ordinato.
L'ordinamento di unione viene comunemente implementato utilizzando una tecnica iterativa, top-down o bottom-up. Nell'implementazione iterativa viene allocato un array ausiliario che viene utilizzato per memorizzare i risultati intermedi durante l'ordinamento dell'elenco. L'approccio top-down, invece, utilizza la ricorsione per scomporre l'elenco in raccolte più piccole di elementi, mentre l'approccio bottom-up utilizza una serie di operazioni di fusione che attraversano i dati verso l'alto.
L'algoritmo ha molte varianti, come il merge sort a quattro vie, il merge sort naturale e il merge sort polifase. Sebbene il merge sort sia più lento del quicksort, che è un altro algoritmo di ordinamento, il suo vantaggio è che il tempo di esecuzione nel caso peggiore è ancora O(n log n). Ciò lo rende adatto per applicazioni in cui l'efficienza è un problema, come sistemi embedded, set di dati di grandi dimensioni e ordinamento di elenchi con operazioni generali di elenchi collegati.
Il merge sort è ampiamente utilizzato in informatica, in particolare nei campi dell'ordinamento, dei database e degli algoritmi. Viene spesso utilizzato nei sistemi operativi per ordinare dati come file e cartelle in un ordine significativo ed è utilizzato anche nello sviluppo di software per semplificare il processo di sviluppo.
Il merge sort è relativamente semplice da comprendere e codificare ed è un utile algoritmo di ordinamento che i principianti possono apprendere come introduzione agli algoritmi.
