#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;
    pivot = rand()%(d-s) + s;
    value = v[pivot];
    pos = s;
    swap(&v[pivot],&v[d]);
    for (i=s;i<d;i++) {
        if (v[i]<value) {
            swap(&v[pos],&v[i]);
            pos++;
        }
    }
    swap(&v[pos],&v[d]);
    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;
}