#include <stdio.h>
#include <stdlib.h>

/*void swap (int *x, int *y) {
    int aux;
    aux = *x;
    *x = *y;
    *y = aux;
}*/

int worker(int *v, int s, int d) {
    int pos,value,pivot,i,x;
    //pivot = rand()%(d-s) + s;
    pivot  = (d+s) / 2;
    value = v[pivot];
    pos = s;
    //swap(&v[pivot],&v[d]);
    x = v[pivot];
    v[pivot] = v[d];
    v[d] = x;
    for (i=s;i<d;i++) {
        if (v[i]<value) {
            //swap(&v[pos],&v[i]);
            x = v[pos];
            v[pos] = v[i];
            v[i] = x;
            pos++;
        }
    }
    //swap(&v[pos],&v[d]);
    x = v[pos];
    v[pos] = v[d];
    v[d] = x;
    return pos;
}


void quicksort(int *v, int s, int d) {
    if (s == d || s > d) return;
    int p = worker(v,s,d);
    quicksort(v,s,p-1);
    quicksort(v,p+1,d);
}

int main()
{
    int v[500000],i,n;
    FILE *f;
    f = fopen("algsort.in","r");
    fscanf(f,"%d",&n);
    for (i=0;i<n;i++) fscanf(f,"%d",&v[i]);
    fclose(f);
    quicksort(v,0,n-1);
    f = fopen("algsort.out","w");
    for (i=0;i<n;i++) fprintf(f,"%d ",v[i]);
    fclose(f);
    return 0;
}