代码

/* Sort n 32-bit unsigned ints in place.
 * LSD radix sort, 4 passes of 8 bits.  The counting pass of the *next* digit is
 * fused into the scatter loop of the current one, so the array is traversed only
 * 5 times instead of 8; the 256-entry digit table keeps all scatter write
 * streams cache resident. */
#include <stdlib.h>
#include <string.h>

void sort(unsigned *a, int n) {
    if (n <= 1) return;
    {   /* already sorted? */
        int ok = 1;
        for (int i = 1; i < n; i++) if (a[i - 1] > a[i]) { ok = 0; break; }
        if (ok) return;
    }
    unsigned *tmp = (unsigned *)malloc((size_t)n * sizeof(unsigned));
    if (!tmp) return;
    static unsigned c[4][256];
    unsigned *src = a, *dst = tmp;

    memset(c[0], 0, sizeof(c[0]));
    {
        const unsigned *__restrict__ s = src;
        for (int i = 0; i < n; i++) c[0][s[i] & 255u]++;
    }
    if (c[0][src[0] & 255u] == (unsigned)n) {   /* pass is a no-op */
        /* nothing to do */
    } else {
        unsigned t = 0;
        for (int i = 0; i < 256; i++) { unsigned x = c[0][i]; c[0][i] = t; t += x; }
        memset(c[1], 0, sizeof(c[1]));
        unsigned *__restrict__ d = dst; const unsigned *__restrict__ s = src;
        int i = 0;
        for (; i + 4 <= n; i += 4) {
            unsigned v0 = s[i], v1 = s[i+1], v2 = s[i+2], v3 = s[i+3];
            d[c[0][v0 & 255u]++] = v0; c[1][(v0 >> 8) & 255u]++;
            d[c[0][v1 & 255u]++] = v1; c[1][(v1 >> 8) & 255u]++;
            d[c[0][v2 & 255u]++] = v2; c[1][(v2 >> 8) & 255u]++;
            d[c[0][v3 & 255u]++] = v3; c[1][(v3 >> 8) & 255u]++;
        }
        for (; i < n; i++) { unsigned v = s[i]; d[c[0][v & 255u]++] = v; c[1][(v >> 8) & 255u]++; }
        { unsigned *t2 = src; src = dst; dst = t2; }
    }
    for (int pass = 1; pass < 4; pass++) {
        int sh = pass << 3;
        if (c[pass][(src[0] >> sh) & 255u] == (unsigned)n) {   /* no-op pass */
            continue;
        }
        unsigned t = 0;
        for (int i = 0; i < 256; i++) { unsigned x = c[pass][i]; c[pass][i] = t; t += x; }
        if (pass < 3) memset(c[pass + 1], 0, sizeof(c[pass + 1]));
        unsigned *__restrict__ d = dst; const unsigned *__restrict__ s = src;
        int i = 0;
        if (pass < 3) {
            for (; i + 4 <= n; i += 4) {
                unsigned v0 = s[i], v1 = s[i+1], v2 = s[i+2], v3 = s[i+3];
                d[c[pass][(v0 >> sh) & 255u]++] = v0; c[pass+1][(v0 >> (sh+8)) & 255u]++;
                d[c[pass][(v1 >> sh) & 255u]++] = v1; c[pass+1][(v1 >> (sh+8)) & 255u]++;
                d[c[pass][(v2 >> sh) & 255u]++] = v2; c[pass+1][(v2 >> (sh+8)) & 255u]++;
                d[c[pass][(v3 >> sh) & 255u]++] = v3; c[pass+1][(v3 >> (sh+8)) & 255u]++;
            }
            for (; i < n; i++) { unsigned v = s[i]; d[c[pass][(v >> sh) & 255u]++] = v; c[pass+1][(v >> (sh+8)) & 255u]++; }
        } else {
            for (; i + 4 <= n; i += 4) {
                unsigned v0 = s[i], v1 = s[i+1], v2 = s[i+2], v3 = s[i+3];
                d[c[3][v0 >> 24]++] = v0;
                d[c[3][v1 >> 24]++] = v1;
                d[c[3][v2 >> 24]++] = v2;
                d[c[3][v3 >> 24]++] = v3;
            }
            for (; i < n; i++) { unsigned v = s[i]; d[c[3][v >> 24]++] = v; }
        }
        { unsigned *t2 = src; src = dst; dst = t2; }
    }
    if (src != a) memcpy(a, src, (size_t)n * sizeof(unsigned));
}

评测结果