代码

void sort(unsigned *a, int n) {
#define N 100000000
#define D 256
#define D1 255
#define cal(w,w2,tw,op)\
p=w2-1;\
for(i=0;i<D;++i)rs[i]=p,p+=tw[i];\
for(i=0;i<N;i+=8){\
	p=w+i;\
	*++rs[p[0]op]=p[0];\
	*++rs[p[1]op]=p[1];\
	*++rs[p[2]op]=p[2];\
	*++rs[p[3]op]=p[3];\
	*++rs[p[4]op]=p[4];\
	*++rs[p[5]op]=p[5];\
	*++rs[p[6]op]=p[6];\
	*++rs[p[7]op]=p[7];\
}
    unsigned b[N],*rs[D],t0[D],t1[D],t2[D],t3[D];
    register unsigned*p,i,x;
    for(i=0; i<D; ++i) {
        t0[i]=0;
        t1[i]=0;
        t2[i]=0;
        t3[i]=0;
    }
    for(i=0; i<N;) {
#define A x=a[i];++t2[x>>16&D1];++t3[x>>24];++i;
        A A A A A A A A
    }
    cal(a,b,t2,>>16&D1);
    cal(b,a,t3,>>24);
    static unsigned z[2048];
    unsigned last=0;int qr=0,k=0;
    for (; k<n; ++k) {
        unsigned now = a[k];
        if ((last^now)>0xffff) {
            last &= 0xffff0000U;
            for (int j=0; j<2048; ++j) {
                unsigned t=z[j];
                switch(__builtin_popcount(t)) {
#define awa(op) \
                   case op: {unsigned q=__builtin_ctz(t); \
                    a[qr++] = j<<5 | q | last; \
                    t &= t-1;}
                   awa(32) awa(31) awa(30) awa(29) awa(28) awa(27) awa(26) awa(25) awa(24) awa(23) awa(22)
awa(21) awa(20) awa(19) awa(18) awa(17) awa(16) awa(15) awa(14) awa(13) awa(12) awa(11) awa(10) awa(9) awa(8)
awa(7) awa(6) awa(5) awa(4) awa(3) awa(2) awa(1)
                }
                z[j]=0;
            }
        }
        last = now;now &= 0xffff;
z[(now)>>5] |= 1<<(now&31);
    }
    last &= 0xffff0000U;
    for (int j=0; j<2048; ++j) {
        unsigned t=z[j];
        while(t) {
            unsigned q=__builtin_ctz(t);
            a[qr++] = j<<5 | q | last;
            t &= t-1;
        }
    }
}

评测结果