#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define digit(numm,i) ( ( numm ) >> ( ( i ) * CHAR_BIT ) & UCHAR_MAX )

void MSD_radix_sort_r ( int a[], int aux[], int first, int last, int d )
{
    if ( d >= 0 )
    {
        int i, count[UCHAR_MAX + 2] = {0};

        for ( i = first; i <= last; i++ )
        {
            count[digit ( a[i], d ) + 1]++;
        }
        for ( i = 1; i <= UCHAR_MAX; i++ )
        {
            count[i] += count[i - 1];
        }
        for ( i = first; i <= last; i++ )
        {
            aux[count[digit ( a[i], d )]++] = a[i];
        }
        for ( i = first; i <= last; i++ )
        {
            a[i] = aux[i - first];
        }

        MSD_radix_sort_r ( a, aux, first, first + count[0] - 1, d - 1 );

        for (i = 0; i < 4; i++)
        {
            MSD_radix_sort_r ( a, aux, first + count[i], first + count[i + 1] - 1, d - 1 );
        }

    }
}
void MSD_radix_sort ( int a[], int first, int last )
{
    int d = sizeof ( int ) - 1;
    int* aux = new int( ( last - first + 1 ) * sizeof ( int ) );

    MSD_radix_sort_r ( a, aux, first, last, d );

    delete ( aux );
}


int main ( void )
{
    int a[11] = {12,324,214,412,31312,312312,12312,123,1,2324,123213};
    MSD_radix_sort( a, 0, 10 );
    for(int i =0; i<11; i++) {
        printf("%d, ", a[i]);
    }
}