const int MSK_SZ = 16;
const int MSK = (1 << MSK_SZ) - 1;

const int MAX_TEMP_SIZE = (int)4e7;

int sz[MSK + 1], ptr[MSK + 1];
int temp[MAX_TEMP_SIZE];

inline void radix(int* arr, int n)
{
    for(int p = 0; p < (int)((8 * sizeof(int)) / MSK_SZ); ++p)
    {
        /*for(int i = 0; i <= MSK; ++i)
            sz[i] = 0;*/

        memset(sz, 0, sizeof(sz));
        memcpy(temp, arr, sizeof(int) * n);

        for(int i = 0; i < n; ++i)
        {
            int value = arr[i];
            int bucket = (value >> (p * MSK_SZ)) & MSK;

            ++sz[bucket];
            //temp[i] = value;
        }

        ptr[0] = 0;

        for(int bucket = 1; bucket <= MSK; ++bucket)
            ptr[bucket] = ptr[bucket - 1] + sz[bucket - 1];

        for(int i = 0; i < n; ++i)
        {
            int value = temp[i];
            int bucket = (value >> (p * MSK_SZ)) & MSK;

            arr[ptr[bucket]] = value;
            ++ptr[bucket];
        }
    }
}