#include <iostream>
#include <vector>
#include <stdlib.h>    
#include <time.h>  
#include <unordered_map>

using namespace std;

int testSortare(vector <long long> &v)
{
    unordered_map <int, int> a;
    int n = v.size();
    for (int i = 1; i < n; i++)
    {
        if (v[i] < v[i-1])
        {
            return -1;
        }
    }
    return 1;
}


void countSort(vector <long long> v, vector <long long> &ans)
{
    int n = v.size();
    if (n != 0)
    {
        long long Max = v[0];
        long long Min = v[0];
        for (int i = 1; i < n; i++)
        {
            Max = max(Max, v[i]);
            Min = min(Min, v[i]);
        }
        for (int i = 0; i< n; i++)
        {
            v[i] -= Min;
        }
    int cnt[Max-Min+1];
    //init
    for (int i = 0; i<= Max-Min; i++)
    {
        cnt[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        cnt[v[i]] ++;
    }
    for (int i = 0; i<= Max-Min; i++)
    {
        for (int j = 1; j <= cnt[i]; j++)
        {
            ans.push_back(i + Min);
        }

    }
    }
}


void generare(int n, vector<long long> &v, bool negativ, long long Max)
{
    srand(time(NULL));
    long long aux;

    for (int i = 1; i<=n;i++)
    {
        if (negativ == 0)
        {
            aux = rand() % (2*Max + 1) - Max;
        }
        else
        {
            aux = rand() % (Max + 1);
        }
        v.push_back(aux);
    }



}

void radixSort(vector<long long> v, vector <long long> &ans, long long base)
{
    int n = v.size();
    // base = 10;
    vector <long long>  bucket[base];
    for (int i = 0; i < n; i++)
    {
        ans.push_back(v[i]);
    }
    if (n != 0)
    {
        long long mod = 1;
        while (true)
        {
            bool next = 0;
            for (int i = 0; i < n; i ++)
            {
                bucket[(ans[i]/mod)%base].push_back(ans[i]);
                if (ans[i]/mod != 0) 
                    next = 1;
            }
            int poz = 0;
            for(int i = 0; i < base; i++)
            {
                int m = bucket[i].size();
                for(int j = 0; j < m; j++)
                {
                    ans[poz] = bucket[i][j]; 
                    poz ++ ;
                }
                bucket[i].clear();
            }
            if (next == 0) break;
            mod *= base;
        }

    }

}




int main()
{
    vector <long long> v;
    vector <long long> ans;
    generare(10, v, 1, 1000000);

    //countSort(v, ans);
    radixSort(v, ans, 256);

    for (int i = 0; i <ans.size(); i++)
    {
        cout<<ans[i]<<" ";
    }


    return 0;
}