#include<iostream>
#include <time.h>
#include<unistd.h>
using namespace std;

int max(int vec[], int n)
{
    int nrMax=vec[0];
    for( int i = 1; i < n; i++ )
    {
        if ( vec[i] > nrMax )
            nrMax = vec[i];
    }

    return nrMax;
}

void Sort(int vec[], int n, int digit)
{
    int finalvec[n];
    int i, count[10] = {0};
    for ( i = 0; i < n; i++)
    {
        count[(vec[i] / digit) % 10]++;
    }
    for ( i = 1; i < 10; i++ )
    {
        count[i] += count[i - 1];
    }
    for ( i = n - 1; i >= 0; i-- )
    {
        finalvec[count[(vec[i] / digit ) % 10] - 1 ] = vec[i];
        count[(vec[i] / digit) % 10 ]--;
    }
    for ( i = 0; i < n; i++)
        vec[i] = finalvec[i];
}

void radix( int vec[], int n)
{
    int ma=max(vec, n);
    for ( int digit = 1; ma / digit > 0; digit *= 10 )
        Sort(vec,n,digit);
}

bool sort_test(int vec[],int n)
{   
    bool ok=true;
    for ( int i=0; i < n-1; i++ )
    {
        if ( vec[i+1] < vec[i] )
            ok = false;
    }
    return ok;
}

int main()
{
    int vec[] = {4,7,43,5534,4,54,5,45,43,46,756,47,6548,67,8678,678,967,8,678,67,8467,8,67,876,84,65,48,47,8467,8,678,67,8,678,674,867,4867,84,78,647,86,78,678,67,867,8,6342,32,32,3,43,4,35,45,3,45,645,65,46,456,54,645,7,658,769,89,87,456,6,5,867,976,87564,645,8,79,6,56,74,856,8,79,8,9867,886,987,97,9,89,879,857,867,9,680,86,987,99,6,98,98,5,78,5,232,6553,221,432,13,45,886,432,4324,5323,43534534,3232};
    int n = sizeof(vec) / sizeof(vec[0]);
    clock_t start = clock();
    radix(vec,n);
    clock_t end = clock();
    double elapsed = double(end - start)/CLOCKS_PER_SEC;
    printf("Time measured: %.9f seconds.\n", elapsed);
    cout<<sort_test(vec,n);
}