#include <iostream>
#include <vector>
#include <fstream>

template<typename DataType>
bool defaultCompare(DataType x, DataType y)
{
    return x<y;
}

template<typename DataType>
void Merge(std::vector< DataType >& arr, int left, int right,bool(*comp)(DataType,DataType)=defaultCompare)//merge the sequences [left,mid] and [mid+1,right]
{
    int mid = (left+right)/2;
    std::vector< DataType > aux;
    int i = left,j = mid+1;
    while(i<=mid && j<=right)
    {
        if( arr[i] < arr[j] )
        {
            aux.push_back(arr[i]);
            i++;
        }
        else{
            aux.push_back(arr[j]);
            j++;
        }
    }
    while(i<=mid)
    {
        aux.push_back(arr[i]);
        i++;
    }
    while(j<=right)
    {
        aux.push_back(arr[j]);
        j++;
    }
    for(int i=0;i<(int)aux.size();i++)
        arr[left+i] = aux[i];
}

template<typename DataType>
void MergeSort(std::vector< DataType >& arr, int left, int right, bool(*comp)(DataType,DataType)=defaultCompare)//sort the vector
{
    if(left < right)
    {
        int mid = (left+right)/2;
        MergeSort(arr,left,mid,comp);
        MergeSort(arr,mid+1,right,comp);
        Merge(arr,left,right,comp);
    }

}

int main()
{
    int n;
    std::vector<int> arr;

    std::ifstream in("algsort.in");

    in >> n;
    for(int i=0;i<n;i++)
    {
        int x;
        in >> x;
        arr.push_back(x);
    }

    in.close();

    MergeSort(arr,0,n-1);

    std::ofstream out("algsort.out");

    for(auto it: arr)
        out << it << ' '; 
    out << '\n';

    out.close();

    return 0;
}