#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <chrono>

bool isPowerOfTwo(int n) {
    return (n & (n - 1)) == 0;
}

void countingSort(std::vector<int>& arr, int exp, int base, bool useBitwise) {
    std::vector<int> output(arr.size());
    std::vector<int> count(base, 0);
    int index;

    for (int i = 0; i < arr.size(); i++) {
        if (useBitwise) {
            index = (arr[i] >> exp) & (base - 1);
        } else {
            index = (arr[i] / exp) % base;
        }
        count[index]++;
    }

    for (int i = 1; i < base; i++) {
        count[i] += count[i - 1];
    }

    for (int i = arr.size() - 1; i >= 0; i--) {
        if (useBitwise) {
            index = (arr[i] >> exp) & (base - 1);
        } else {
            index = (arr[i] / exp) % base;
        }
        output[count[index] - 1] = arr[i];
        count[index]--;
    }

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

void radixSort(std::vector<int>& arr, int base) {
    bool useBitwise = isPowerOfTwo(base);
    int maxNum = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxNum / exp > 0; exp *= base) {
        int bitExp = useBitwise ? __builtin_ctz(exp) : exp;
        countingSort(arr, bitExp, base, useBitwise);
    }
}

int main() {
    std::ifstream inFile("algsort.in");
    std::ofstream outFile("output.txt");
    std::vector<int> arr;
    int base = 10, n;
    int value;

    inFile>>n;

    for(int i = 1;i<=n;i++){
        inFile >> value;
        arr.push_back(value);
    }

    //auto start = std::chrono::high_resolution_clock::now();

    radixSort(arr, base);

   // auto end = std::chrono::high_resolution_clock::now();
   // std::chrono::duration<double> duration = end - start;

    for (int num : arr) {
        outFile << num << " ";
    }

   // std::cout << "Time taken to sort: " << duration.count() << " seconds." << std::endl;

    return 0;
}