#include <iostream>

int findMedian(int* arr, int size){
    for (int i = 0; i < size - 1; ++i){
        for (int j = i + 1; j < size; ++j){
            if (arr[i] > arr[j]){
                std::swap(arr[i], arr[j]);
            }
        }
    }
    return arr[(size - 1) / 2];
}

int QuickSelect(int* arr, int size, int k);

int GetPivot(int* arr, int size){
    if (size < 5){
        return findMedian(arr, size);
    }
    int* medians = new int[(size + 4) / 5];
    int medsize = 0;
    for (int i = 0; i < size - size % 5; i += 5){
        medians[medsize++] = findMedian(arr + i, 5);
    }
    if (size % 5){
        medians[medsize++] = findMedian(arr + size - 1 - size % 5, size % 5);
    }
    int medianOfMedians = QuickSelect(medians, medsize, (medsize - 1) / 2);
    delete[] medians;
    return medianOfMedians;
}

void Partition(int* arr, int size, int pivot){
    int start = 0, mid = size - 1, fin = size - 1;
    while (start != mid){
        if (arr[start] >= pivot){
            std::swap(arr[start], arr[mid]);
            mid--;
        }
        else{
            start++;
        }
    }
    while (mid != fin){
        if (arr[mid] > pivot){
            std::swap(arr[mid], arr[fin]);
            fin--;
        }
        else{
            mid++;
        }
    }
}

int QuickSelect(int* arr, int size, int k){
    if (size == 1){
        return arr[0];
    }
    int pivot = GetPivot(arr, size);
    Partition(arr, size, pivot);
    int count_less = 0, count_not_more = 0;
    while (arr[count_less] < pivot){
        count_less++;
        count_not_more++;
    }
    while (arr[count_not_more] <= pivot){
        count_not_more++;
    }
    if (k >= count_not_more){
         return QuickSelect(arr + count_not_more, size - count_not_more, k - count_not_more);
    }
    if (k < count_less){
        return QuickSelect(arr, count_less, k);
    }
    return pivot;

}

void QuickSort(int* arr, int size){
    if (size == 1){
        return;
    }

    int pivot = QuickSelect(arr, size, (size - 1) / 2);
    Partition(arr, size, pivot);
    int count_less = 0, count_not_more = 0;
    while (arr[count_less] < pivot){
        count_less++;
    }
    while (arr[count_not_more] <= pivot){
        count_not_more++;
    }
    if (count_less != 0){
        QuickSort(arr, count_less);
    }
    if (size - count_not_more != 0) {
        QuickSort(arr + count_not_more, size - count_not_more);
    }
}

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int n;
    std::cin >> n;

    int* arr = new int[n];
    for (int i = 0; i < n; i++){
        std::cin >> arr[i];
    }

    QuickSort(arr, n);
    for (int i = 0; i < n; i++){
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
    delete[] arr;
    return 0;
}