#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
using namespace std;

vector<int> merge(vector<int> in1, vector<int> in2) {
    vector<int> out;
    int size = in1.size()*2;
    int i,j=0,k=0;
    for (i=0;i<size;i++) {
        if (in1[j] < in2[k]) {
            out.push_back(in1[j]);
            j++;
        }
        else {
            out.push_back(in2[k]);
            k++;
        }
        if (j==size/2 || k==size/2)
            break;
    }
    if (j == size/2 && k<size/2) {
        for (i=k;i<size/2;i++) {
            out.push_back(in2[i]);
        }
    }
    if (k == size/2 && j<size/2) {
        for (i=j;i<size/2;i++) {
            out.push_back(in1[i]);
        }
    }
    return out;
}

vector<int> ord(vector<int> vect) {
    vector<int> dev;
    if (vect.size() == 2) {
        if (vect[0]>vect[1]) {
            dev.push_back(vect[1]);
            dev.push_back(vect[0]);
        }
        else {
            dev.push_back(vect[0]);
            dev.push_back(vect[1]);
        }
        return dev;
    }

    vector<int> a1;
    vector<int> a2;
    int i;

    for (i=0;i<vect.size();i++) {
        if (i<vect.size()/2)
            a1.push_back(vect[i]);
        else
            a2.push_back(vect[i]);
    }
    a1 = ord(a1);
    a2 = ord(a2);
    return merge(a1,a2);
}

int main() {
    ifstream fin("num.txt");
    char numb[7];
    vector<int> numeros;
    int i,j;
    for (i=0;i<=65535;i++) {
        fin.getline(numb,7);
        numeros.push_back(atoi(numb));
    }
    FILE *f = fopen("prueba.txt","w");
    vector<int> result = ord(numeros);
    for (i=0;i<65536;i++) {
        fprintf(f,"%d\n",result[i]);
    }
    fclose(f);
    printf("Time: %d\n", clock());
    return 0;
}