/**
Sortare prin interclasare
Divide et impera care la sortarea unei secvente o imparte in ce 2 jumatati si
la revenirea din recursivitate le interclaseaza pe cele 2, revenind mereu
cu o secventa sortata.

Facand mereu impartirea la jumatate, dupa log injumatatiri se ajunge la secvente
dintr-un singur element.

Astfel arborele de autoapeluri are inaltimea log.

Dar la fiecare nivel al sau se afla toate elementele sirului si fiecare dintre ele
participa la o singura interclasare pe nivel.

Astfel avem o(n) la fiacare nivel.

In total n log

Insa este necesar un vector suplimentar de memorie folosit in timpul interclasarii
si trebuie sa il declaram global.

**/
#include <fstream>
using namespace std;
int v[500010], w[500010];
int n, i;

void interclaseaza(int st, int mid, int dr) {
    int i=st, j = mid+1;
    int k = st-1;
    while (i<=mid && j<=dr) {
        if (v[i] < v[j]) {
            w[++k] = v[i++];
        } else {
            w[++k] = v[j++];
        }
    }
    for (;i<=mid;i++) {
        w[++k] = v[i];
    }
    for (;j<=dr;j++) {
        w[++k] = v[j];
    }

    for (i=st;i<=dr;i++)
        v[i] = w[i];

}

void sorteaza(int st, int dr) { /// sa sortez elementele de la indicele st la indicele dr
    if (st < dr) {
        int mid = (st+dr)/2;
        sorteaza(st, mid);
        sorteaza(mid+1, dr);
        /// astfel am cele 2 jumatati sortate dar vreau sa am tot sortat
        /// reunesc cele 2 jumatati si optim fac asta cu o interclasare a lor
        interclaseaza(st, mid, dr);

        /// sort(v+st, v+dr+1); cu asta in loc de interclasare avem n * (log parrat)

        /// presupune ca are sortata secventa de la st la mid,
        /// sortata si pe cea de ma mid+1 la dr, si le interclaseaza

    }
}



int main () {

    ifstream fin("algsort.in");
    ofstream fout("algsort.out");

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

    sorteaza(1, n);

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


}