#include <bits/stdc++.h>
using namespace std;
class Sorting{
int n;
int *arr;
public:
Sorting(int n,int p[]){
this->n = n;
arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = p[i];
}
}
void printArray(){
for(int i=0;i<n;i++){
cout << arr[i] << " ";
}
cout <<"\n";
}
void BubbleSort(){
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(arr[i] > arr[j]){
swap(arr[i],arr[j]);
}
}
}
}
void SelectionSort(){
for(int i=0;i<n;i++){
int min_val = arr[i];
int idx = i;
for(int j=i+1;j<n;j++){
if(arr[j] < min_val){
min_val = arr[j];
idx = j;
}
}
swap(arr[i],arr[idx]);
}
}
void InsertionSort(){
for(int i=1;i<n;i++){
int j = i - 1;
int k = i;
while(j >= 0){
if(arr[k] < arr[j]){
swap(arr[k],arr[j]);
k = j;
}
j--;
}
}
}
void merge(int i,int j,int k){
int t[k-i+1];
int i1=i,i2=j+1,k1=0;
while(i1 <= j && i2 <= k){
if(arr[i1] < arr[i2]){
t[k1] = arr[i1];
k1++;
i1++; // 2 5 1 16 1 17 3 18
}
else{
t[k1] = arr[i2];
k1++;
i2++;
}
}
while(i1 <= j){
t[k1] = arr[i1];
k1++;
i1++;
}
while (i2 <= k)
{
t[k1] = arr[i2];
k1++;
i2++;
}
for(int idx = i;idx <= k ;idx++){
cout << t[idx-i] <<" ";
arr[idx] = t[idx - i];
}
cout << "\n";
}
void MergeSort(int l,int r){
if(l < r){
int mid = l+(r-l)/2;
MergeSort(l,mid);
MergeSort(mid + 1,r);
merge(l,mid,r);
}
}
};
int main(){
int n;
cin >> n;
int a[n];
for(int i=0;i<n;i++) cin >> a[i];
Sorting s(n,a);
s.MergeSort(0,n-1);
s.printArray();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNsYXNzIFNvcnRpbmd7CiAgICBpbnQgbjsKICAgIGludCAqYXJyOwogICAgcHVibGljOgogICAgU29ydGluZyhpbnQgbixpbnQgcFtdKXsKICAgICAgICB0aGlzLT5uID0gbjsKICAgICAgICBhcnIgPSBuZXcgaW50W25dOwogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspewogICAgICAgICAgICBhcnJbaV0gPSBwW2ldOwogICAgICAgIH0KICAgIH0KICAgIHZvaWQgcHJpbnRBcnJheSgpewogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspewogICAgICAgICAgICBjb3V0IDw8IGFycltpXSA8PCAiICI7CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwiXG4iOwogICAgfQogICAgdm9pZCBCdWJibGVTb3J0KCl7ICAgICAgICAgCiAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKyl7CiAgICAgICAgICAgIGZvcihpbnQgaj1pKzE7ajxuO2orKyl7CiAgICAgICAgICAgICAgICBpZihhcnJbaV0gPiBhcnJbal0pewogICAgICAgICAgICAgICAgICAgIHN3YXAoYXJyW2ldLGFycltqXSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICB2b2lkIFNlbGVjdGlvblNvcnQoKXsKICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKXsKICAgICAgICAgICAgaW50IG1pbl92YWwgPSBhcnJbaV07CiAgICAgICAgICAgIGludCBpZHggPSBpOwogICAgICAgICAgICBmb3IoaW50IGo9aSsxO2o8bjtqKyspewogICAgICAgICAgICAgICAgaWYoYXJyW2pdIDwgbWluX3ZhbCl7CiAgICAgICAgICAgICAgICAgICAgbWluX3ZhbCA9IGFycltqXTsKICAgICAgICAgICAgICAgICAgICBpZHggPSBqOwogICAgICAgICAgICAgICAgfSAKICAgICAgICAgICAgfQogICAgICAgICAgICBzd2FwKGFycltpXSxhcnJbaWR4XSk7CiAgICAgICAgfQogICAgfQogICAgdm9pZCBJbnNlcnRpb25Tb3J0KCl7ICAgICAgICAKICAgICAgICBmb3IoaW50IGk9MTtpPG47aSsrKXsKICAgICAgICAgICAgaW50IGogPSBpIC0gMTsKICAgICAgICAgICAgaW50IGsgPSBpOwogICAgICAgICAgICB3aGlsZShqID49IDApewogICAgICAgICAgICAgICAgaWYoYXJyW2tdIDwgYXJyW2pdKXsKICAgICAgICAgICAgICAgICAgICBzd2FwKGFycltrXSxhcnJbal0pOwogICAgICAgICAgICAgICAgICAgIGsgPSBqOyAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBqLS07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICB2b2lkIG1lcmdlKGludCBpLGludCBqLGludCBrKXsKICAgICAgICBpbnQgdFtrLWkrMV07CiAgICAgICAgaW50IGkxPWksaTI9aisxLGsxPTA7CiAgICAgICAgd2hpbGUoaTEgPD0gaiAmJiBpMiA8PSBrKXsKICAgICAgICAgICAgaWYoYXJyW2kxXSA8IGFycltpMl0pewogICAgICAgICAgICAgICAgdFtrMV0gPSAgYXJyW2kxXTsKICAgICAgICAgICAgICAgIGsxKys7CiAgICAgICAgICAgICAgICBpMSsrOyAgICAgICAgICAgICAgIC8vIDIgNSAxIDE2IDEgMTcgMyAxOCAKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgdFtrMV0gPSBhcnJbaTJdOwogICAgICAgICAgICAgICAgazErKzsKICAgICAgICAgICAgICAgIGkyKys7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgd2hpbGUoaTEgPD0gail7CiAgICAgICAgICAgIHRbazFdID0gYXJyW2kxXTsKICAgICAgICAgICAgazErKzsKICAgICAgICAgICAgaTErKzsKICAgICAgICB9CiAgICAgICAgd2hpbGUgKGkyIDw9IGspCiAgICAgICAgewogICAgICAgICAgICB0W2sxXSA9IGFycltpMl07CiAgICAgICAgICAgIGsxKys7CiAgICAgICAgICAgIGkyKys7CiAgICAgICAgfQogICAgICAgIGZvcihpbnQgaWR4ID0gaTtpZHggPD0gayA7aWR4KyspewogICAgICAgIAljb3V0IDw8IHRbaWR4LWldIDw8IiAiOwogICAgICAgICAgICBhcnJbaWR4XSA9IHRbaWR4IC0gaV07CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgIlxuIjsKICAgIH0KICAgIHZvaWQgTWVyZ2VTb3J0KGludCBsLGludCByKXsKICAgICAgICBpZihsIDwgcil7CiAgICAgICAgICAgIGludCBtaWQgPSBsKyhyLWwpLzI7CiAgICAgICAgICAgIE1lcmdlU29ydChsLG1pZCk7CiAgICAgICAgICAgIE1lcmdlU29ydChtaWQgKyAxLHIpOwogICAgICAgICAgICBtZXJnZShsLG1pZCxyKTsKICAgICAgICB9CiAgICB9Cn07CmludCBtYWluKCl7CiAgICBpbnQgbjsKICAgIGNpbiA+PiBuOwogICAgaW50IGFbbl07CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKSBjaW4gPj4gYVtpXTsKICAgIFNvcnRpbmcgcyhuLGEpOwogICAgcy5NZXJnZVNvcnQoMCxuLTEpOwogICAgcy5wcmludEFycmF5KCk7CiAgICByZXR1cm4gMDsKfQ==