mergesort - SalvDC

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
///Procedure
///NB: Con c++11 il nome merge non crea conflitto con la funzione merge()!
void merge(vector <int>& v, int destra, int centro, int sinistra) {
	vector <int> aux;                               ///Creo un vettore
	aux.resize(sinistra+1);                         ///Assegno al vettore dimensione sx+1 (tutti gli elementi +1)
	int i,j;
	for (i = centro+1; i > destra; i--)             ///Scorri dalla posizione centro+1 fino all'inizio dell'array
		aux.at(i-1) = v.at(i-1);                    ///Carica gli elementi in maniera simmetrica rispetto agli elementi del vector in entrata
	for (j = centro; j < sinistra; j++)             ///Scorri dalla posizione centro fino alla fine dell'array
		aux.at(sinistra+centro-j) = v.at(j+1);      ///Carica gli elementi a partire dal fondo della porzione + centro - j '1° passo parte dell'estremo - 2° passo estremo - 1....' e caricali nell'array partendo dalla posizione successiva al centro
	for (int k = destra; k <= sinistra; k++)        ///Scorri dall'inizio alla fine
		if (aux.at(j) < aux.at(i))                  ///Se l'elemento aux[j]<aux[i] RICORDA: i vale dx all'uscita del primo ciclo e j vale sx dall'uscita del secondo ciclo, sto confrontando i due estremi di aux!
			v.at(k) = aux.at(j--);                  ///Carica in v l'elemento minore
		else
			v.at(k) = aux.at(i++);                  ///Carica in v l'elemento minore
    ///Piccola nota
    ///Non ho necessità di deallocare il contenitore Vector poichè il loro scopo è proprio quello di allontanare il programmatore da eventuali errori che hanno a che fare con un uso improprio della memoria
}
void mergesort(vector <int>& a, int destra, int sinistra) {
	if (destra<sinistra) {                      ///Divido finchè non arrivo alla singola unità
		int centro = (destra+sinistra)/2;       ///Trova il centro
		mergesort(a, destra, centro);           ///Scendi nella parte destra
		mergesort(a, centro+1, sinistra);       ///Scendi nella parte sinistra
		merge(a, destra, centro, sinistra);     ///Ordina le sotto-porzioni
	}
}

void impera(vector <int> a,vector <int> b,vector <int>&c)
{
    int i=0,j=0;
    while(i<a.size()&&j<b.size())               ///Scorri finche uno dei 2 vettori 'a' e 'b' non è terminato
    {
        if(a.at(i)<b.at(j))                     ///Determina il più piccolo tra i due elementi confrontati
            c.push_back(a.at(i++));             ///Carica il dato in 'c'
        else
            c.push_back(b.at(j++));             ///Carica il dato in 'c'
    }
    ///A questo punto uno dei due vettori è terminato allora:

    while(i<a.size())                           ///Se ci sono ancora elementi di 'a'
        c.push_back(a.at(i++));                 ///Carica il dato in 'c'

    while(j<b.size())                           ///Se ci sono ancora elementi di 'b'
        c.push_back(b.at(j++));                 ///Carica il dato in 'c'
}
int main()
{
    vector <int> a={10,9,8,7,6,5};      ///Vector pre-caricato da ordinare
    vector <int> b={11,21,35,3,1};      ///Vector pre-caricato da ordinare
    vector <int> c;                     ///Vector da creare con a + b
    mergesort(a,0,a.size()-1);          ///Ordino a
    mergesort(b,0,b.size()-1);          ///Ordino b
    cout<<"\tBenvenuto nel Programma 'MERGE SORT'"<<endl<<endl;;
    cout<<"Il vettore 'a' ordinato \x82:";
    for(auto x:a)                       ///Scorro il vettore a con un Range-For
        cout<<" "<<x;
    cout<<endl;
    cout<<"Il vettore 'b' ordinato \x82:";
        for(auto x:b)                   ///Scorro il vettore b con un Range-For
        cout<<" "<<x;
    impera(a,b,c);                      ///Fondo i due array nell'array c
    cout<<endl<<endl<<"Il vettore 'c' fuso tra i vettori 'a' e 'b' \x82:";
    for(auto x:c)                       ///Scorro il vettore c con un Range-For
        cout<<" "<<x;
    cout<<endl<<endl<<endl;
    return 0;
}