//
//  main.cpp
//  Quicksort
//
//  Created by Alex Petrache on 30/10/14.
//  Copyright (c) 2014 Alex Petrache. All rights reserved.
//

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

int a[500001];

int partition(int st,int dr){
    int pivot=a[(st+dr)/2];
    while(st<=dr){
        while(a[st]<pivot)
            st++;
        while(a[dr]>pivot)
            dr--;
        if(st<=dr){
            swap(a[st],a[dr]);
            st++;
            dr--;
        }
    }
    return st;
}

void quicksort(int st, int dr){
    int index=partition(st,dr);
    if(st<index-1)
        quicksort(st, index-1);
    if(dr>index)
        quicksort(index, dr);
}

int main(int argc, const char * argv[])
{
    int n,i;
//    ifstream f("/Users/alexpetrache/Documents/Programare/Xcode/Arhiva Educationala/Quicksort/Quicksort/algsort.in");
//    ofstream g("/Users/alexpetrache/Documents/Programare/Xcode/Arhiva Educationala/Quicksort/Quicksort/algsort.out");
    ifstream f("algsort.in");
    ofstream g("algsort.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    quicksort(1,n);
    
    for(i=1;i<=n;i++)
        g<<a[i]<<" ";
    return 0;
}