/*Riscrivere il Merge Sort utilizzando il contenitore Vector ed un iteratore.*/
#include<iostream>
#include<vector>
using namespace std;

void Merge(vector<int>&elementi, short inizio, short fine)
{
    vector<int>v;
    short mediano = (inizio + fine) / 2;

    vector<int>::iterator it_l{ elementi.begin() }, it_r{ elementi.begin() + mediano }, it_mid{ elementi.begin() + mediano }, it_end{ elementi.end() };
    while (it_l != it_mid && it_r != it_end)
    {
        v.push_back((*it_l <= *it_r) ? *it_l++ : *it_r++);
    }

    v.insert(v.end(), it_l, it_mid);
    v.insert(v.end(), it_r, it_end);

    for (auto x : v)
        cout << x << '\t';
    cout << endl;
}

void Merge_Sort(vector<int>elementi, short inizio, short fine)
{
    if (inizio < fine)
    {
        short mediano = (inizio + fine) / 2;
        Merge_Sort(elementi, inizio, mediano);
        Merge_Sort(elementi, mediano + 1, fine);
        Merge(elementi, inizio, fine);
    }
}

int main()
{
    vector<int>elementi = { 4,5,7,2,8,0,9,1,2,4 };

    for (vector<int>::iterator i = elementi.begin(); i != elementi.end(); ++i)
        cout << *i << '\t';
    cout << endl;

    Merge_Sort(elementi, 0, (short)elementi.size());

    /*for (auto x : elementi)
        cout << x << '\t';
    cout << endl;*/

    return 0;
}