#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void Merge(int *arr,int low,int mid,int high){
int numA=mid-low+1;
int numB=high-mid;
int numC=high-low+1;
int *A=(int *) malloc(sizeof(int)*numA);
int *B=(int *) malloc(sizeof(int)*numB);
int *C=(int *) malloc(sizeof(int)*numC);
for(int i=0;i<numA;i++)
A[i]=arr[low+i];
for(int j=0;j<numB;j++)
B[j]=arr[mid+1+j];
int i=0;
int j=0;
int k=0;
while(i<numA && j<numB){
if(A[i]<B[j])
C[k++] = A[i++];
else C[k++]=B[j++];
}
while(i<numA)
C[k++]=A[i++];
while(j<numB)
C[k++]=B[j++];
for(int i=0;i<k;i++)
arr[low+i]=C[i];
free(A);
free(B);
free(C);
}
void MergeSort(int *arr,int low,int high){
if(low<high){
int mid=low+(high-low)/2;
MergeSort(arr,low,mid);
MergeSort(arr,mid+1,high);
Merge(arr,low,mid,high);
}
}
void BinaryInsertionSort(int *v,int low_arr,int high_arr){
int ind;
int aux,elem,low,high,mid;
for(int i=low_arr;i<=high_arr;i++){
low=0;
high=i;
elem=v[i];
while(low<high){
mid=low+(high-low)/2;
if(v[mid]<=elem)
low=mid+1;
else high=mid;
}
if(high!=i) {
for (int j = i; j > high; j--) {
v[j] = v[j - 1];
}
v[high] = elem;
}
}
}
int Partition(int *arr,int low,int high){
int aux;
int pivot=low;
while(low<=high){
while(arr[low]<arr[pivot]) {
low++;
}
while(arr[high]>arr[pivot]) {
high--;
}
if(low<high){
aux=arr[low];
arr[low]=arr[high];
arr[high]=aux;
low++;
high--;
}
else break;
}
aux=arr[high];
arr[high]=arr[pivot];
arr[pivot]=aux;
return high;
}
void HybridQuickSortBinaryInsertionSort(int *arr,int low,int high,int threshold){
if(low<high){
if(high-low<threshold)
BinaryInsertionSort(arr,low,high);
else {
int rand_index = rand() % (high - low) + low;
int aux = arr[low];
arr[low] = arr[rand_index];
arr[rand_index] = aux;
int p = Partition(arr, low, high);
HybridQuickSortBinaryInsertionSort(arr, low, p - 1,threshold);
HybridQuickSortBinaryInsertionSort(arr, p + 1, high,threshold);
}
}
}
void MakeHeap(int *Heap,int sizeHeap,int curr_index){
int aux;
while(curr_index<sizeHeap/2){
if(Heap[curr_index]>=Heap[2*curr_index+1] && (curr_index*2+2>sizeHeap || Heap[curr_index]>=Heap[curr_index*2+2]))
return;
if(Heap[2*curr_index+1]>=Heap[curr_index] && (curr_index*2+2>sizeHeap || Heap[2*curr_index+1]>=Heap[2*curr_index+2])){
aux=Heap[curr_index];
Heap[curr_index]=Heap[2*curr_index+1];
Heap[2*curr_index+1]=aux;
curr_index=(curr_index<<1)+1;
}
else{
aux=Heap[curr_index];
Heap[curr_index]=Heap[2*curr_index+2];
Heap[2*curr_index+2]=aux;
curr_index=(curr_index<<1)+2;
}
}
}
void BuildHeapBottomUp(int *Heap,int startHeap,int stopHeap){
for(int i=stopHeap/2;i>=startHeap;i--)
MakeHeap(Heap,stopHeap,i);
}
void HeapSort(int *Heap,int startHeap,int stopHeap){
BuildHeapBottomUp(Heap,startHeap,stopHeap);
int aux;
for(int i=startHeap;i<stopHeap-1;i++){
aux=Heap[stopHeap-(i-startHeap)];
Heap[stopHeap-(i-startHeap)]=Heap[startHeap];
Heap[startHeap]=aux;
MakeHeap(Heap,stopHeap-(i-startHeap)-1,startHeap);
}
}
void IntroSort(int *arr,int low,int high,int threshold,int maxdepth){
if((high-low)<threshold)
BinaryInsertionSort(arr,low,high);
else if(maxdepth==0)
HeapSort(arr,low,high);
else{
int rand_index = rand() % (high - low) + low;
int aux = arr[low];
arr[low] = arr[rand_index];
arr[rand_index] = aux;
int p = Partition(arr, low, high);
IntroSort(arr,low,p-1,threshold,maxdepth-1);
IntroSort(arr,p+1,high,threshold,maxdepth-1);
}
}
int main() {
srand(time(NULL));
freopen("algsort.in","r",stdin);
freopen("algsort.out","w",stdout);
int n;
scanf("%d",&n);
int *arr=(int *) malloc(sizeof(int)*n);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
//MergeSort(arr,0,n-1);
// HybridQuickSortBinaryInsertionSort(arr,0,n-1,35);
int depth;
for(depth=1;depth<n;depth<<=1);
IntroSort(arr,0,n-1,35,depth);
for(int i=0;i<n;i++)
printf("%d ",arr[i]);
free(arr);
return 0;
}