Merge Sort

1. Cos'è il Merge Sort?

Il Merge Sort è un efficiente algoritmo di ordinamento basato sul paradigma del Divide et Impera (dividi et impera). L'idea fondamentale consiste nel suddividere ricorsivamente il vettore non ordinato in sotto-vettori più piccoli fino a raggiungere sotto-strutture di dimensione unitaria (già ordinate per definizione), per poi procedere alla loro fusione (merge) ordinata ricomponendo la struttura globale.

2. Meccanismo di Funzionamento e Codice C++

L'algoritmo si compone di due funzioni principali: una funzione ricorsiva di divisione (`mergeSort`) e una funzione di supporto per la fusione (`merge`) che unisce due sotto-array ordinati in un unico vettore coerente.

                // Implementazione del Merge Sort in C++
                #include <vector>
                #include <iostream>

                void merge(std::vector<int>& v, int left, int mid, int right) {
                int n1 = mid - left + 1;
                int n2 = right - mid;

                std::vector<int> L(n1), R(n2);
                for (int i = 0; i < n1;
                i++) L[i] = v[left + i];
                for (int j = 0; j < n2;
                j++) R[j] = v[mid + 1 + j];

                int i = 0, j = 0, k = left;
                while (i < n1 && j < n2) {
                if (L[i] <= R[j]) { v[k++] = L[i++]; }
                else { v[k++] = R[j++]; }
                }
                while (i < n1) v[k++] = L[i++];
                while (j < n2) v[k++] = R[j++];
                }

                void mergeSort(std::vector<int>& v, int left, int right) {
                if (left >= right) return;
                int mid = left + (right - left) / 2;
                mergeSort(v, left, mid);
                mergeSort(v, mid + 1, right);
                merge(v, left, mid, right);
                }
            

3. Analisi della Complessità

Complessità Temporale $\mathcal{O}(N \log N)$ (Tutti i casi): Grazie alla suddivisione binaria ricorsiva e alla fase di fusione lineare, il Merge Sort garantisce prestazioni eccellenti anche nel caso peggiore, superando nettamente gli algoritmi elementari quadratici.
Complessità Spaziale $\mathcal{O}(N)$: Richiede memoria di supporto aggiuntiva per allocare i sotto-vettori temporanei durante le operazioni di fusione.

4. Simulatore Interattivo: Esecuzione Merge Sort

Inserisci una sequenza di numeri interi separati da virgola per testare l'ordinamento tramite Merge Sort e verificare le metriche di esecuzione.

merge-sort@nexus-core:~# Merge Sort Simulator

Vettore Numerico (separato da virgole):

> Configura il vettore numerico per avviare la simulazione interattiva del Merge Sort.

1. Cos'è il Merge Sort?

2. Meccanismo di Funzionamento e Codice C++

3. Analisi della Complessità

4. Simulatore Interattivo: Esecuzione Merge Sort

Gestione della Privacy e dei Cookie