/**
500 000 la patrat
250 000 000 000 = 250 de miliarde
/2 = 125 de miliarde
Cand vreau sa estimez timpul de calcul urmaresc:
- daca numarul de pasi este de cateva milioane (maxim, maxim 100 000 000) atunci timpul de rulare e instant (sub 1 secunda)

**/


/**
    exista algoritmi de sortare cu timp de calcul de ordin n * logaritm in baza 2 din n
    logaritm = exponent
    logaritm in baza 2 dintre-un numar a = la ce putere trebuie ridicat 2 pentru a ajunge la a

    Notez direct log = logaritm in baza 2

    log 8 = 3 deoarece 2 la a 3 - a face 8
    log 1024 = 10 deoarece 2 la a 10 - a face 1024

    Aproximativ
    log 1000 = 10
    log 2000 = 11
    log 4000 = 12
    log 8000 = 13
    log 16000 = 14
    log 32000 = 15
    log 64000 = 16
    log 128000 = 17
    log 256000 = 18
    log 512000 = 19
    log 1000000 = cam 20

 n = 500 000
 n patrat = 125 miliarde
 n log n = 500 000 * 20 = 10 000 000 = 20 de milioane
 Un algoritm care ar face un astfel de numar de pasi ar rula instant.

 Vo ajunge sa invatam sa scriem de mana astfel de algoritmi.
 Deocamdata va prezint modul in care folosim un astfel de algoritm preimprementat in una dintre bibliotecile limbajului

**/
#include<fstream>
#include<algorithm>
using namespace std;
int v[500010];
int n, i, j, aux, sortat;
int main () {
    ifstream fin ("algsort.in");
    ofstream fout("algsort.out");

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    sort(v+1, v+n+1);  // v + 1 = un pointer (adresa primului element luat in calcul la sortare)

    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";

    return 0;
}


/**

#include<fstream>
using namespace std;
int v[500010];
int n, i, j, aux, sortat;
int main () {
    ifstream fin ("algsort.in");
    ofstream fout("algsort.out");

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    do {
        sortat = 1;
        for (i=1;i<n;i++)
            if (v[i] > v[i+1]) {
                aux = v[i];
                v[i] = v[i+1];
                v[i+1] = aux;
                sortat = 0;
            }
    } while (sortat == 0);
    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";

    return 0;
}

**/