/* a stands for source array;
   b stands for destination array;
   n stands for array size;
   k stands for range of values of integral key, must be a constant;
   d stands for "digit", which is the operation used for extracting the
     integral key from each array item.
*/
#define rsort_macro(a,b,n,k,d) { \
    int c[k] = {}; \
 \
    for (int i = 0; i < n; ++i) { \
        ++c[a[i] d]; \
    } \
    for (int i = 1; i < k; ++i) { \
        c[i] += c[i-1]; \
    } \
    for (int i = n-1; i >= 0; --i) { \
        b[--c[a[i] d]] = a[i]; \
    } \
}

/* count sort by least significant byte 0..7,
   then by 8..15 and so on...
*/
void rsort_int(int *arr, int num)
{
    int *arr_ = malloc(num * sizeof(int));

    for (int shr = 0; shr < sizeof(int) * 8; shr += 8) {
        rsort_macro(arr, arr_, num, 0x100, >> shr & 0xff);
        memcpy(arr, arr_, num * sizeof(int));
    }

    free(arr_);
}

/* dep stand for significant depth,
   which is length of leading substring, taken into account,
   e.g. if dep == 3, "iiia" and "iiib" are treated as equal.
*/
void rsort_str(unsigned char **arr, int num, int dep)
{
    unsigned char **arr_ = malloc(num * sizeof(unsigned char *));

    while (dep--) {
        rsort_macro(arr, arr_, num, 0x100, [dep]);
        memcpy(arr, arr_, num * sizeof(unsigned char *));
    }

    free(arr_);
}

/* radix sorting of double precision floating point numbers:
   1. by mantissa, just like integers;
   2. by exponent, just like integers;
   (1.111... * 2^n < 1.000... * 2^(n+1))
   3. when sorted by absolute value, collect in reverse order,
      stack negative ones on the left side
      (descending by absolute value == ascending by signed value),
      and positive ones on the right side
      (descending-descending == ascending).
*/
void rsort_dbl(double *arr, int num)
{
    double *arr_ = malloc(num * sizeof(double));

    for (int shr = 0; shr < 52; shr += 13) {
        rsort_macro(arr, arr_, num, 0x2000, >> 13 & 0x1fff);
        memcpy(arr, arr_, num * sizeof(double));
    }
    rsort_macro(arr, arr_, num, 0x800, >> 52 & 0x7ff);
    memcpy(arr, arr_, num * sizeof(double));

    for (int i = num-1, i_ = 0, _i = num-1; i >= 0; --i) {
        if (arr[i] < 0)
            arr_[i_++] = arr[i];
        else
            arr_[_i--] = arr[i];
    }
    memcpy(arr, arr_, num * sizeof(double));

    free(arr_);
}