[C++] Spiegazione funzione ricorsiva di ordinamento

[ireon]

Ragazzi sto impazzendo, non riesco a capire come funziona questa funzione ricorsiva... Qualcuno può gentilmente spiegarmelo?

void merge_sort(vector<int>& a, int from, int to)
{
   if (from == to) return;
   int mid = (from + to) / 2;
   merge_sort(a, from, mid);
   merge_sort(a, mid + 1, to);
   merge(a, from, mid, to);
}

[Alex'87]

void merge_sort(vector<int>& a, int from, int to)
{
   /* Immagino che from indichi l'inizio del sottoarray sinistro mentre to la fine di quello 
    * di destra. Quando i due indici si accavallano interrompi la ricorsione.  
    */
   if (from == to) return;

   /* Cerca l'elemento che sta a metà del sottoarray, sarà l'elemento pivot */
   int mid = (from + to) / 2;

   /* richiama ricorsivamente la funzione sulla prima metà del sottoarray */
   merge_sort(a, from, mid);

   /* richiama ricorsivamente la funzione sulla seconda metà del sottoarray */
   merge_sort(a, mid + 1, to);

   /* qui è dove i vari sottoarray creati vengono rimessi assieme in modo ordinato */
   merge(a, from, mid, to);
}

Graficamente funziona così:


http://en.wikipedia.org/wiki/Merge_sort

[ireon]

Si, ok, ma non riesco a capire come fa la funzione richiamando se stessa a ordinare i due sotto vettori, cioè la funzione richiama se stessa due volte, infatti:

merge_sort(a, from, mid);
merge_sort(a, mid + 1, to);

La prima chiamata ordina il primo sottovettore e la seconda il secondo sottovettore, ma in che modo vengono ordinati? Non riesco a raffigurarmelo...

[Alex'87]

Originariamente inviato da ireon
La prima chiamata ordina il primo sottovettore e la seconda il secondo sottovettore, ma in che modo vengono ordinati? Non riesco a raffigurarmelo...

Dimentichi la chiamata a merge, è lì il "succo" di tutto...

[ireon]

Dimentichi la chiamata a merge, è lì il "succo" di tutto...

Si, ok, però merge funziona solamente se i due sottovettori sono completamente ordinati, quindi merge_sort (a,from,mid) riordina il primo sottovettore, merge_sort(a,mid+1,to) riordina il secondo sottovettore e quando i due sottovettori sono completamente ordinati viene chiamata merge che unisce i due vettore in un unico vettore completamente ordinato...

[Alex'87]

Originariamente inviato da ireon
Si, ok, però merge funziona solamente se i due sottovettori sono completamente ordinati, quindi merge_sort (a,from,mid) riordina il primo sottovettore, merge_sort(a,mid+1,to) riordina il secondo sottovettore e quando i due sottovettori sono completamente ordinati viene chiamata merge che unisce i due vettore in un unico vettore completamente ordinato...

Hai letto la pagina di wikipedia che ti ho linkato? C'è questa immagine che mi sembra piuttosto chiara:


Guarda che la chiamata a merge non è effettuata una volta sola (come credo che invece che tu abbia capito)!

[ireon]

In pratica guardando lo schema, inizialmente viene chiamata la ricorsività di merge_sort(a,from,mid) e merge_sort (a,mid+1,to), poi quando il vettore disordinato iniziale è stato scomposto in singoli elementi viene di volta in volta chiamata merge che riscostruisce quindi il vettore ordinato... È così che funziona? Poi però non capisco quando viene verificato il caso base, ovvero from == to, guardando sempre lo schema quand'è che from è uguale a to?