#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

template <typename T>
static
void carica (vector<T>& v)
{
    string temp;
    stringstream* _in;
    T tdbl;
    bool ancora = true;

    cout << "Immetti i numeri da ordinare." << endl
        << "Premi invio senza immettere nulla per terminare" << endl;

    do
    {
        cout << "Numero da inserire: ";
        getline(cin, temp);
        if (temp == "")
            ancora = false;
        else
        {
            _in = new stringstream(temp);
            *_in >> tdbl;
            if (!_in->fail())
                v.push_back(tdbl);
            delete _in;
        }
    } while (ancora);
}

template <typename T>
static
void stampa (const vector<T>& v)
{
    for (vector<T>::const_iterator i = v.begin(); i != v.end(); ++i)
    {
        if (i != v.begin()) cout << " ";
        cout << *i;
    }
    cout << endl;
}

template <typename T>
static
vector<T> ordina (const vector<T>& v)
{
    vector<T>::size_type sz = v.size();

    if (sz <= 1)
        return v;
    else
    {
        //Split phase
        vector<T> sx(v.begin(), v.begin() + (sz / 2));
        vector<T> dx(v.begin() + (sz / 2), v.end());

        //Recursive phase
        sx = ordina(sx);
        dx = ordina(dx);

        //Merge phase
        vector<T> mix;
        mix.reserve(sz);
        vector<T>::const_iterator si = sx.begin(), send = sx.end();
        vector<T>::const_iterator di = dx.begin(), dend = dx.end();
        while (si != send && di != dend)
            mix.push_back((*si < *di) ? *(si++) : *(di++));
        while (si != send)
            mix.push_back(*(si++));
        while (di != dend)
            mix.push_back(*(di++));
        return mix;
    }
}

int main (int argc, char* argv[])
{
    cout << "Questo programma ordina un elenco di numeri" << endl;
    vector<double> lista;

    carica(lista);
    cout << endl << "Lista inserita:" << endl;
    stampa(lista);
    cout << endl;

    cout << "Lista ordinata:" << endl;
    stampa(ordina(lista));
    cout << endl;

    system("pause");
    return 0;
}