#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const char NUME_FISIER_INTRARE[] = "algsort.in";
const char NUME_FISIER_IESIRE[] = "algsort.out";
const int  QUICKSORT_THRESHOLD = 3;

vector<int> *citesteNumere(const char filename[]){
	ifstream fin(filename);
	int n;
	fin >> n;
	vector<int> *numere = new vector<int>(n);

	for(int i = 0; i < (*numere).size(); ++i){
		fin >> (*numere)[i];
	}
	fin.close();

	return numere;
}

int median(vector<int> *numere, int start, int end){
	int center = start + (end-start)/2;
	if((*numere)[start] > (*numere)[center]){
		swap((*numere)[start], (*numere)[center]);
	}
	if((*numere)[center] > (*numere)[end]){
		swap((*numere)[center], (*numere)[end]);
	}
	if((*numere)[start] > (*numere)[center]){
		swap((*numere)[start], (*numere)[center]);
	}
	
	swap((*numere)[start+1], (*numere)[center]);

	return (*numere)[start+1];
}

int partitie(vector<int> *numere, int start, int end){
	int pivot = median(numere, start, end);
	int i = start + 1; //primul element este deja la locul lui, al doilea este pivotul iar while=ul incrementa
				//i-ul si apoi il va folosi
	int j = end;       //ultimul element este deja la locul lui, while-ul va incrementa j-ul si apoi il va folosi
	
	while(true){
		while((*numere)[++i] < pivot);
		while((*numere)[--j] > pivot);


		if(i >= j){
			break;
		}
		swap((*numere)[i], (*numere)[j]);
	}
	swap((*numere)[start+1], (*numere)[j]);

	return j;
}

void insertionSort(vector<int> *numere){
	for(int i = 1; i < (*numere).size(); ++i){
		int j = i;
		while(j > 0 && (*numere)[j-1] > (*numere)[j]){
			swap((*numere)[j-1], (*numere)[j]);
			--j;
		}
	}
}

void quickSort(vector<int> *numere, int start, int end){
	if(start >= end - QUICKSORT_THRESHOLD){
		insertionSort(numere);
		return;
	}

	int pivot = partitie(numere, start, end);
	quickSort(numere, start    , pivot - 1);
	quickSort(numere, pivot + 1, end);
}

void sort(vector<int> *numere){
	//wrapper quicksort
	quickSort(numere, 0, (*numere).size() - 1);
}

void scrieNumere(const char filename[], vector<int> *numere){
	//scrie numerele
	ofstream fout(filename);
	for(int i = 0; i < (*numere).size(); ++i){
		fout << (*numere)[i] << " ";
	}
	fout.close();
}

int main(int argc, char *argv[]){
	vector<int> *numere;
	
	numere = citesteNumere(NUME_FISIER_INTRARE);
	sort(numere);
	scrieNumere(NUME_FISIER_IESIRE, numere);

	delete numere;
	return 0;
}